题目描述（中等难度）

229. Majority Element II - 图1

找出数组中数量超过 n/3 的数字，n 是数组的长度。

解法一

题目要求是 O(1) 的空间复杂度，我们先用 map 写一下，看看对题意的理解对不对。

map 的话 key 存数字，value 存数字出现的个数。如果数字出现的次数等于了 n/3 + 1 就把它加到结果中。

  1. public List<Integer> majorityElement(int[] nums) {
  2.     int n = nums.length;
  3.     HashMap<Integer, Integer> map = new HashMap<>();
  4.     List<Integer> res = new ArrayList<>();
  5.     for (int i = 0; i < n; i++) {
  6.         int count = map.getOrDefault(nums[i], 0);
  7.         //之前的数量已经是 n/3, 当前数量就是 n/3 + 1 了
  8.         if (count == n / 3) {
  9.             res.add(nums[i]);
  10.         }
  11.         //可以提前结束
  12.         if (count == 2 * n / 3 || res.size() == 2) {
  13.             return res;
  14.         }
  15.         map.put(nums[i], count + 1);
  17.     }
  18.     return res;
  19. }

解法二

169 题 我们做过找出数组的中超过 n/2 数量的数字，其中介绍了摩尔投票法，这里的话可以改写一下，参考 这里。

首先看一下 169 题 我们是怎么做的。

我们假设这样一个场景，在一个游戏中，分了若干个队伍，有一个队伍的人数超过了半数。所有人的战力都相同，不同队伍的两个人遇到就是同归于尽，同一个队伍的人遇到当然互不伤害。

这样经过充分时间的游戏后，最后的结果是确定的，一定是超过半数的那个队伍留在了最后。

而对于这道题，我们只需要利用上边的思想，把数组的每个数都看做队伍编号，然后模拟游戏过程即可。

group 记录当前队伍的人数，count 记录当前队伍剩余的人数。如果当前队伍剩余人数为 0，记录下次遇到的人的所在队伍号。

对于这道题的话，超过 n/3 的队伍可能有两个，首先我们用 group1 和 group2 记录这两个队伍，count1 和 count2 分别记录两个队伍的数量，然后遵循下边的游戏规则。

将数组中的每一个数字看成队伍编号。

group1 和 group2 首先初始化为不可能和当前数字相等的两个数，将这两个队伍看成同盟，它俩不互相伤害。

然后遍历数组中的其他数字，如果遇到的数字属于其中的一个队伍，就将当前队伍的数量加 1。

如果某个队伍的数量变成了 0，就把这个队伍编号更新为当前的数字。

否则的话，将两个队伍的数量都减 1。

  1. public List<Integer> majorityElement(int[] nums) {
  2.     int n = nums.length;
  3.     long group1 = (long)Integer.MAX_VALUE + 1;
  4.     int count1 = 0;
  5.     long group2 = (long)Integer.MAX_VALUE + 1;
  6.     int count2 = 0;
  7.     for (int i = 0; i < n; i++) {
  8.         if (nums[i] == group1) {
  9.             count1++;
  10.         } else if (nums[i] == group2) {
  11.             count2++;
  12.         } else if (count1 == 0) {
  13.             group1 = nums[i];
  14.             count1 = 1;
  15.         } else if (count2 == 0) {
  16.             group2 = nums[i];
  17.             count2 = 1;
  18.         } else {
  19.             count1--;
  20.             count2--;
  21.         }
  22.     }
  24.     //计算两个队伍的数量,因为可能只存在一个数字的数量超过了 n/3
  25.     count1 = 0;
  26.     count2 = 0;
  27.     for (int i = 0; i < n; i++) {
  28.         if (nums[i] == group1) {
  29.             count1++;
  30.         }
  31.         if (nums[i] == group2) {
  32.             count2++;
  33.         }
  34.     }
  35.     //只保存数量大于 n/3 的队伍
  36.     List<Integer> res = new ArrayList<>();
  37.     if (count1 > n / 3) {
  38.         res.add((int) group1);
  39.     }
  41.     if (count2 > n / 3) {
  42.         res.add((int) group2);
  43.     }
  44.     return res;
  45. }

上边有个技巧就是先将 group 初始化为一个大于 int 最大值的 long 值，这样可以保证后边的 if 条件判断中，数组中一定不会有数字和 group相等，从而进入后边的更新队伍编号的分支中。除了用 long 值，我们还可以用包装对象 Integer，将 group 初始化为 null 可以达到同样的效果。

当然，不用上边的技巧也是可以的，我们可以先在 nums 里找到两个不同的值分别赋值给 group1 和 group2 中即可，只不过代码上不会有上边的简洁。

总

解法一算是通用的解法，解法二的话看起来比较容易，但如果只看上边的解析，然后自己写代码的话还是会遇到很多问题的，其中 if 分支的顺序很重要。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情