问题

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

  1. 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
  2. 输出: 2

限制：

  1. 1 <= 数组长度 <= 50000

解答一

利用哈希表，记录每个数字出现的次数

  1. class Solution {
  2.      public int majorityElement(int[] nums) {
  3.          int mLen = nums.length/2;
  4.          Map<Integer, Integer> map = new HashMap<>(mLen + 1);
  5.          for(int i = 0; i < nums.length; i ++)
  6.              map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
  8.          for(Integer key: map.keySet())
  9.              if(map.get(key) > mLen)
  10.                  return key;
  12.          return -1; 
  13.     }
  14. }

执行用时：14ms
内存消耗：45.1MB

解答二

对数组进行排序，再计算每个数字出现的次数

class Solution{
 public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int count = 1;
        int num = nums[0];
        int mLen = nums.length / 2;
        for(int i = 1;i < nums.length; i ++){
            if(nums[i] == num){
                count ++;
            }else{
                count = 1;
                num = nums[i];
            }
            if(count > mLen)
                break;
        }
        return num;
    }     
}

执行用时 :3 ms, 在所有 Java 提交中击败了35.73%的用户。
内存消耗 :42.8 MB, 在所有 Java 提交中击败了100.00%的用户。

摩尔投票法（最佳解答）

摩尔投票法：
票数和： 由于众数出现的次数超过数组长度的一半；若记 众数 的票数为 +1+1 ，非众数 的票数为 -1−1 ，则一定有所有数字的 票数和 > 0>0 。
票数正负抵消： 设数组 nums 中的众数为 xx ，数组长度为 nn 。若 nums 的前 aa 个数字的 票数和 = 0=0 ，则 数组后 (n-a)(n−a) 个数字的 票数和一定仍 >0（即后 (n-a)(n−a) 个数字的 众数仍为 xx ）。

作者：jyd
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/

class Solution {
    public int majorityElement(int[] nums) {
        int x = nums[0];
        int votes = 1;

        for(int i = 1; i < nums.length; i ++){
            votes = nums[i] == x? votes+1 : votes-1;
            if(votes < 0){
                x = nums[i];
                votes = 1;
            }
        }
        return x;
    }
}

执行用时 :2 ms, 在所有 Java 提交中击败了74.55%的用户
内存消耗 :42.6 MB, 在所有 Java 提交中击败了100.00%的用户

优化后的代码

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0;
        int votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

算法流程：以 [1, 2, 2, 1 , 2] 为例
初始化: x = 0, votes = 0
num = 1 : 得分 votes ：0， 更换大多数， 大多数为： 1，得分 votes : 1
num = 2 : 与大多数不同，得分 - 1， 得分votes ：0，当前大多数为 ： 1
num = 2 : 得分 votes：0，更换大多数，大多数为：2，得分 votes ：1
num = 1 ：与大多数不同，得分 -1， 得分 votes ： 0，当前大多数为：2
num = 2 : 得分 votes : 0 ，更换大多数，大多数为 2， 得分 votes : 1

易懂版

class Solution {
    public int majorityElement(int[] nums) {
        int times = 0;
        int res = 0;
        for (int i = 0; i < nums.length; i ++){
            if (times == 0){
                res = nums[i];
                times = 1;
                continue;
            }
            if ( nums[i] != res )
                times --;
            else
                times ++;
        }
        return res ;
    }
}