java 投票算法_Boyer and Moore Fast majority vote algorithm(快速选举算法)

问题来来自于leetcode上的一道题目，https://leetcode.com/problems/majority-element/，大意是是找出一个数组中，出现次数超过一个半的数字，要求是O(n)的算法。

这道题的解法来自于  Boyer-Moore Majority Vote Algorithm   http://www.cs.utexas.edu/~moore/best-ideas/mjrty/。

算法原理

以下是论文原文的片段

翻译过来大致是：

假设有一群投票的人，每个人都会投票个某个候选人。为了选择最终赢的选取的候选人，可以采用这样的选举方式：每个投票人找到其他的投票人，并且这个投票人支持的候选不同于自己的支持的候选人，PK过后，这一对投票人同时出局。经过全部的PK之后，那么还没有出局的投票人支持的候选人，就有可能是最终的选举胜利者(获得半数以上的选票)。最后，选举主席，需要检查这位可能赢得选举的候选人的票数，来确认他是否赢得了选举。

因为leetcode上的题目，已经确认了majority number始终是存在的。那么统计票数的一个步骤实际可以省略了。

算法实现

以下是论文的原文

用java代码实现是

public int majorityElement(int[] nums) {

int candIndex = -1;

int k = 0;

for ( int i = 0; i < nums.length ; i++) {

if ( k == 0 ){

candIndex = i;

k = 1;

}else{

if ( nums[candIndex] == nums[i]) {

k++;

}else {

k --;

}

}

}

return nums[candIndex];

}

总结

以上是生活随笔为你收集整理的java 投票算法_Boyer and Moore Fast majority vote algorithm(快速选举算法)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。