LeetCode229-求众数II

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/majority-element-ii/

中文链接：https://leetcode-cn.com/problems/majority-element-ii/

题目详述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

1
2
输入: [3,2,3]
输出: [3]

示例 2:

1
2
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

题目详解

  • LeetCode169-求众数 是求出现次数大于 ⌊ n/2 ⌋ 的元素，最多有一个。本题是求出现次数大于 ⌊ n/3 ⌋ 的元素，最多有两个。
  • 解决方法是相同的，都是采用摩尔投票算法。
  • 不过本题不保证满足条件的元素一定存在，所以最后还需要进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class LeetCode_00229 {

    public List<Integer> majorityElement(int[] nums) {
        // 摩尔投票算法
        int[] candidate = new int[2];
        int[] cnt = new int[2];
        for (int num : nums) {
            if (num == candidate[0]) {
                ++cnt[0];
            } else if (num == candidate[1]) {
                ++cnt[1];
            } else if (cnt[0] == 0) {
                candidate[0] = num;
                cnt[0] = 1;
            } else if (cnt[1] == 0) {
                candidate[1] = num;
                cnt[1] = 1;
            } else {
                --cnt[0];
                --cnt[1];
            }
        }
        // 重新统计判断是否满足要求
        Arrays.fill(cnt, 0);
        for (int num : nums) {
            if (num == candidate[0]) {
                ++cnt[0];
            } else if (num == candidate[1]) {
                ++cnt[1];
            }
        }
        // 满足要求才加入结果集
        List<Integer> res = new ArrayList<>();
        if (cnt[0] > nums.length / 3) {
            res.add(candidate[0]);
        }
        if (cnt[1] > nums.length / 3) {
            res.add(candidate[1]);
        }
        return res;
    }
}