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[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 |
如果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表示
联系客服