题目描述（中等难度）

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

解法一

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

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

解法二

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

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

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

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

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

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

否则的话，将两个队伍的数量都减 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;
  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.             count1 = 1;
  14.         } else if (count2 == 0) {
  15.             group2 = nums[i];
  16.             count2 = 1;
  17.         } else {
  18.             count1--;
  19.             count2--;
  20.         }
  21.     }
  23.     //计算两个队伍的数量,因为可能只存在一个数字的数量超过了 n/3
  24.     count1 = 0;
  25.     count2 = 0;
  26.     for (int i = 0; i < n; i++) {
  27.         if (nums[i] == group1) {
  28.         }
  30.             count2++;
  31.         }
  32.     }
  33.     //只保存数量大于 n/3 的队伍
  34.     List<Integer> res = new ArrayList<>();
  35.     if (count1 > n / 3) {
  36.         res.add((int) group1);
  37.     }
  39.     if (count2 > n / 3) {
  40.         res.add((int) group2);
  41.     }
  42.     return res;

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

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

总

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

添加好友一起进步~

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