剑指 Offer 39. 数组中出现次数超过一半的数字

  1. class Solution {
  2.     public int majorityElement(int[] nums) {
  3.         int x = 0, votes = 0;
  4.         for(int num : nums){
  5.             if(votes == 0) x = num;
  6.             votes += num == x ? 1 : -1;
  7.         }
  8.         return x; 
  9.     }
  11.      public int majorityElement2(int[] nums) {
  12.         int x = 0, votes = 0, count = 0;
  13.         for(int num : nums){
  14.             if(votes == 0) x = num;
  15.             votes += num == x ? 1 : -1;
  16.         }
  17.         // 验证 x 是否为众数
  18.         for(int num : nums)
  19.             if(num == x) count++;
  20.         return count > nums.length / 2 ? x : 0; // 当无众数时返回 0
  21.     }
  22. // 作者：jyd
  23. // 链接：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/
  24. }

本题常见的三种解法：

哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出众数 。时间和空间复杂度O(N) 。
数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法。
摩尔投票法：
设输入数组 nums 的众数为 x ，数组长度为 n 。

推论一： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。

推论二： 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余
(n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x。