229. Majority Element II

1. Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

2. Examples

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

3. Constraints

• 1 <= nums.length <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/majority-element-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

5.1. 统计法

空间复杂度为O(n)

class Solution {
  public List<Integer> majorityElement(int[] nums) {
    HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();

    for (int i = 0; i < nums.length; i++) {
      if (cnt.containsKey(nums[i])) {
        cnt.put(nums[i], cnt.get(nums[i]) + 1);
      } else {
        cnt.put(nums[i], 1);
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int x : cnt.keySet()) {
      if (cnt.get(x) > nums.length / 3) {
        ans.add(x);
      }
    }

    return ans;
  }
}

5.2. Moore 投票法

空间复杂度为O(1)

class Solution {
  public List<Integer> majorityElement(int[] nums) {
    // Moore 投票法

    // 由于题目要求超过n/3次，所以答案最多有3-1=2个，需要有两个候选者
    int cand1 = 0;
    int count1 = 0;
    int cand2 = 0;
    int count2 = 0;

    // 投票环节
    for(int num : nums) {
      // 对候选者1投票
      if(num == cand1) {
        count1++;
        continue;
      }

      // 对候选者2投票
      if(num == cand2) {
        count2++;
        continue;
      }

      // 如果上述条件都不符合则将count为0的候选者进行置换
      if(count1 == 0) {
        cand1 = num;
        count1++;
        continue;
      }
      if(count2 == 0) {
        cand2 = num;
        count2++;
        continue;
      }

      // 如果上述几个条件全部不符合，则将两个候选者的票都-1
      count1--;
      count2--;
    }

    // 计数环节
    count1 = 0;
    count2 = 0;
    for(int num : nums) {
      if(num == cand1) {
        count1++;
      }
      if(num == cand2) {
        count2++;
      }
    }

    List<Integer> list = new ArrayList<>();

    // 这里有个坑，题目要求出现必须超过ｎ／3个（向上取整），等于也不行。
    if(count1 * 3 > nums.length) {
      list.add(cand1);
    }

    // 防止类似三个0的坑爹用例
    if(cand1 != cand2 && count2 * 3 > nums.length) {
      list.add(cand2);
    }
    return list;
  }
}