NO.229 求众数II 中等
思路一：摩尔投票法 本题是上一题169的姊妹题，本题没有说一定存在这个”较多的元素”。而且本题的众数的数量需要讨论。
n/k的众数最多有k-1个，本题的符合大于n/3的众数最多有3-1=2个。就像169题中要求的大于n/2，很容易就想到最多存在一个。
知道了本题最多存在两个符合要求的元素，那么根据摩尔头条进行改进：仍然是先定下候选人A、B，然后分别有一个计数器count1、count2。
遍历所有元素，如果当前元素投票给A(和A相等)则count1++，如果是投票给B则count++。
如果不投给A和B，检查两个计数器是否等于0，如果等于0则让被投票的num作为新的候选人且相应的计数器置为1；如果计数器都不等于0，则两个计数器都-1。
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
| public List<Integer> majorityElement(int[] nums) {
List<Integer> res=new ArrayList<>();
if (nums==null||nums.length==0)return res;
int candidate1=0,candidate2=0,count1=0,count2=0;
for (int num : nums) {
if (num==candidate1){
count1++;
continue;
}
if (num == candidate2) {
count2++;
continue;
}
if (count1 == 0) {
candidate1=num;
count1++;
continue;
}
if (count2 == 0) {
candidate2=num;
count2++;
continue;
}
count1--;
count2--;
}
count1=count2=0;
for (int num : nums) {
if (num == candidate1){
count1++;
} else if (num == candidate2) {
count2++;
}
}
if (count1>nums.length/3)res.add(candidate1);
if (count2>nums.length/3)res.add(candidate2);
return res;
}
|
时间复杂度：O(n) 两次遍历
本人菜鸟，有错误请告知，感激不尽！
更多题解和学习记录博客:博客、github