leetcode-169. 多数元素

JAVA解法

class Solution {
    public int majorityElement(int[] nums) {
        //假设第一个元素的票数
       int count = 1;
        //假设第一个元素为当选人
       int candidate = nums[0];
       for(int i=0;i<nums.length; i++){
           //如果数组遍历过程中，有元素和当选人元素一样，就加一
           if(nums[i] == candidate){
               count++;
           }else{
                //如果没有就减一
               count--;
           }
            //如果票数为0的话就更换当选人
           if(count == 0){
               //更换当选人
               candidate = nums[i];
                //票数重新置为1
               count = 1;
           }
       }
       return candidate;
    }
}

leetcode原题： 169. 多数元素

解法分析

借助leetcode一位大佬的解释：

摩尔投票法也叫做同归于尽法，下面举一个三国的例子： 比如有甲、乙、丙三个军队进行厮杀，先假设甲的人数最多，然后发现最后甲和乙的人数全部阵亡，就只剩下丙了，那么这个丙就是人数最多的一个。

摩尔投票法：刚开始有甲乙丙三个候选人，谁都不知道是谁当选，因为票数都是 0，先假设数组的甲（这里是数组的第一个元素）为当选人，票数是 1，然后遍历整个数组，如果遇到甲的，票数就加一，如果遇到不是甲的，票数就减一，直到甲的票数为 0，甲的票数为 0 就更换候选人，然后继续比较，遍历到数组的最后一个元素就是当选人。然后票数等于 0 就更换当选人。

这道题的题目是假设数组是存在多数元素的，这个条件非常重要，也就是说这个数组中必定有元素是超过 n/2 的，也就是说用摩尔投票法找出来的众数一定是超过 n/2 的。