题目

类型：Array
image.png

解题思路

这道题用 map 方法去做很简单，但是题目描述要求要达到线性的时间复杂度，还有常量级的空间复杂度。
这个就变得有点难了，不过有更好的算法可以达到题目的要求——摩尔投票法。
https://leetcode-cn.com/problems/majority-element-ii/solution/liang-fu-dong-hua-yan-shi-mo-er-tou-piao-fa-zui-zh/
看视频会理解的快点

代码

  1. class Solution {
  2.     public List<Integer> majorityElement(int[] nums) {
  3.         // 创建返回值
  4.         List<Integer> res = new ArrayList<>();
  5.         if (nums == null || nums.length == 0) return res;
  6.         // 初始化两个候选人candidate，和他们的计票
  7.         int cand1 = nums[0], count1 = 0;
  8.         int cand2 = nums[0], count2 = 0;
  10.         // 摩尔投票法，分为两个阶段：配对阶段和计数阶段
  11.         // 配对阶段
  12.         for (int num : nums) {
  13.             // 投票
  14.             if (cand1 == num) {
  15.                 count1++;
  16.                 continue;
  17.             }
  18.             if (cand2 == num) {
  19.                 count2++;
  20.                 continue;
  21.             }
  23.             // 第1个候选人配对
  24.             if (count1 == 0) {
  25.                 cand1 = num;
  26.                 count1++;
  27.                 continue;
  28.             }
  29.             // 第2个候选人配对
  30.             if (count2 == 0) {
  31.                 cand2 = num;
  32.                 count2++;
  33.                 continue;
  34.             }
  36.             count1--;
  37.             count2--;
  38.         }
  40.         // 计数阶段
  41.         // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
  42.         count1 = 0;
  43.         count2 = 0;
  44.         for (int num : nums) {
  45.             if (cand1 == num) count1++;
  46.             else if (cand2 == num) count2++;
  47.         }
  49.         if (count1 > nums.length / 3) res.add(cand1);
  50.         if (count2 > nums.length / 3) res.add(cand2);
  52.         return res;
  53.     }
  54. }