摩尔投票法最佳实践

Posted on Edited on Views:

摩尔投票算法基础理论及最佳实践

会议大厅站满了投票代表，每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的（所选的候选人不同）两个人，会打一架，并且会同时击倒对方。

这里意见不合的两个人促成了算法的核心思想：对拼消耗

显而易见，如果一个人拥有的选票比其它所有人加起来的选票还要多的话，这个候选人将会赢得这场“战争”，当混乱结束，最后剩下的那个代表（可能会有多个）将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数（选票都未超过一半），那么最后站在那的代表（一个人）并不能代表所有的选票的大多数。因此，当某人站到最后时，需要统计他所选的候选人的选票是否超过一半（包括倒下的），来判断选票结果是否有效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
   求多数元素(众数)
      摩尔投票法
   */
   public int majorityElement1(int[] nums) {
       int count = 0;//当前记录出现次数
       int current = -1;//当前记录值
       for (int num : nums) {
           if (num == current) count++;
           if (num != current) {
               if (count == 0) {
                   current = num;
               } else {
                   count--;
               }
           }
       }
       return current;
   }