多数派问题

from http://blog.csdn.net/joylnwang/article/details/7081575

2011.12

假设数组v[1...n]中的每个元素v[i](1<=i<=n)对应于m个元素中的一个，这里m个元素用整数1～m表示，现在需要判断在数组v中是否有某个元素出现的次数，超过了半数。如果，v[1...n]对应于n张选票，1～m对应于m个候选人，这个问题实际上就是要判断是否有候选人的得票数严格过半（大于n/2）。

对于实际应用场景，我们可以用下面的方法解决该问题，用一个m元素的数组，分别记录各候选人的得票数，同时记录当前得票最多的候选人的得票总数，然后依次读入v[1...n]这n张选票，对每张选票对应的候选人的得票数加1。所有选票处理完毕后，判断得票数最多的候选人的得票数，是否大于n/2。该算法的时间复杂度为O(n)，空间复杂度为O(m)。一般情况，候选人的数量m为常量，所以该算法可以高效的求解。但是如果m的情况不清楚，那么此方法就存在比较大的问题。初始阶段，由于无法确定m的规模，在程序运行过程中，可能会出现候选人的数量，大于预先分配数组的情况，此时就涉及到m数组的重新分配和内存的拷贝，比较极端的情况，如果m=n，那么就可能涉及候选人数组的多次重新分配，极大的影响算法的效率。

Robert S.Boyer和J Strother Moore两位牛人（就是BM算法的提出者），在《MJRTY-A Fast Majority Vote Algorithm》一文中，提出了一个巧妙算法，使得我们即使不知道m的具体情况，也可以在O(n)时间复杂度，O(1)空间复杂度内，判断是否有候选人的得票数过半。该算法在运行过程中，需要两个临时变量c和t，c记录当前可能得票数过半的候选人编号，t记录该候选人的净超出次数。对于c而言，除了可以等于1～m中的任何值之外，还有另一种状态，我们把其叫做未知状态，用于表示当前任何候选人的得票数都不可能过半（程序中可以用0，或者-1表示），t的最小值为0，程序开始运行时c为未知状态（c=0），t=0，然后按照如下方法处理投票数组v。

• 对于v[i](1<=i<=n)，如果c此时为未知状态，则c=v[i]，t=1，递增i。
• 如果c==v[i]，++t，递增i。
• 如果c!=v[i]，--t，如果t==0，将c置为未知状态，递增i。
• 所有投票处理完毕后，如果c为未知状态，则说明不存在任何候选人的得票数过半，否则重新遍历数组v，统计候选人c的实际得票总数，如果c的得票数确实过半，则c就是最终结果。
  

举例说明，假设v[1...8]={1,2,1,1,3,1,4,4}，投票的数量为8，候选人的数量为4，此时用上述算法处理投票数据的过程如下表所示，这里未知状态用'?'表示

i	1	2	3	4	5	6	7	8
v[i]	1	2	1	1	3	1	4	4
c	1	?	1	1	1	1	1	?
t	1	0	1	2	1	2	1	0

程序运行的最终结果，c处于未知状态，说明对于投票数组v，不存在任何候选人的得票数过半。

如果v[1...9]={1,2,1,1,3,1,4,4,1}，此时c的最后状态为1，重新遍历数组v，查看候选人1的得票数是否确实过半，统计结果1出现了5次，大于9/2，所以候选人1的票数过半。

如果v[1...9]={1,2,1,1,3,1,4,4,4}，此时c的最后状态为4，统计数组v，发现4出现了3次，小于9/2，所以对于投票集合v，不存在候选人的票数过半。

该算法通过第一次遍历数组v，找到了可能候选人c，此时对于数组v，的票过半的候选人要么是c，要么就不存在任何人得票过半。这个结论并非那么显而易见，需要进行说明。首先，投票的顺序不影响计票的结果，所以无论v[1...9]={1,1,1,1,1,2,3,4,4}，还是v[1...9]={1,2,1,3,1,4,1,4,1}，最终得票过半数的都是候选人1，所以我们可以根据自己的需要，调整选票的先后顺序。假设第一遍遍历数组v后的结果c=c'，此时我们可以这样构造投票数组中投票的顺序，一张c'，一张其他候选人的投票，一张c'，一张其他候选人的投票，……，如此构建得到v[1...n]={c',x,c',x,……}，其中x代表除c'外其他任何候选人的投票，这样我们就可以将c'与x对应起来，因为c'的出现次数大于n/2，所以c'的总数必然大于其他所有候选者的票数之和，所以用此种方法排列投票，最后必然出现c',c',c',……连续出现的情况，按照本算法，之前的所有配对的c',x处理完毕的结果为c=?，因为后续出现的都是c'，所以运行的最终结果必然是c=c'，也就说明，如果v中某个候选人c'的得票数超过半数，运行结果必然有c=c'。

如果c最终为不确定状态，此时得票最多的候选人c'的票数最多也只能为n/2，此时不存在任何候选人得票数过半。

当然，也存在没有任何人得票数过半，且c不为未知状态的情况。所以，算法需要重新统计候选人c的真实得票数，以确定其是否真的得票数过半。

下面是算法代码，其中候选人的编号从0开始，未知状态用-1表示

[cpp] view plain copy

1. int Majority(const int array[], size_t array_size)  
2. {  
3.     unsigned int i;  
4.   
5.     int candidate = -1;  
6.     unsigned int times = 0;  
7.   
8.     for(i = 0; i < array_size; ++i)  
9.     {  
10.         if(candidate == -1)  
11.         {  
12.             candidate = array[i];  
13.             times = 1;  
14.             continue;  
15.         }  
16.   
17.         if(candidate == array[i])  
18.         {  
19.             ++times;  
20.             continue;  
21.         }  
22.   
23.         if(--times == 0)  
24.         {  
25.             candidate = -1;  
26.         }  
27.     }  
28.   
29.     if(candidate == -1)  
30.     {  
31.         return -1;  
32.     }  
33.   
34.     for(i = 0, times = 0; i < array_size; ++i)  
35.     {  
36.         if(array[i] == candidate)  
37.         {  
38.             ++times;  
39.         }  
40.     }  
41.   
42.     if(times > array_size / 2)  
43.     {  
44.         return candidate;  
45.     }  
46.   
47.     return -1;  
48. }  

该算法在计算得票过半候选人的时候需要扫描投票数组两遍，所以对于候选人数量固定的情况，效率不如传统算法。但是对于候选人情况不确定的情况，该算法可以不受影响。特别是该算法在解决多数派问题时的思路，确实值得我们学习。