leetcode-majority-element-ii

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/majority-element-ii/

　　找到数组中所有出现次数超过n/3的数

题目分析

　　跟majority element题类似，我们可以借助两对变量保存答案，还是基于统计+抵消的思路，最后还要验证ans1和ans2出现次数是否超过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
43
44
45
46
47
48
49
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        int len = nums.length;
        if (len == 0) {
            return ans;
        }
        if (len == 1) {
            ans.add(nums[0]);
            return ans;
        }
        int ans1 = nums[0];
        int c1 = 0;
        int ans2 = nums[0];
        int c2 = 0;
        for (int n : nums) {
            if (n == ans1) {
                c1++;
            } else if (n == ans2) {
                c2++;
            } else if (c1 == 0) {
                ans1 = n;
                c1 = 1;
            } else if (c2 == 0) {
                ans2 = n;
                c2 = 1;
            } else {
                c1--;
                c2--;
            }
        }
        c1 = 0;
        c2 = 0;
        for (int n : nums) {
            if (n == ans1) {
                c1++;
            } else if (n == ans2) {
                c2++;
            }
        }
        if (c1 > len / 3) {
            ans.add(ans1);
        }
        if (c2 > len / 3) {
            ans.add(ans2);
        }
        return ans;
    }
}