-
Notifications
You must be signed in to change notification settings - Fork 0
/
MajorityElementII.java
37 lines (37 loc) · 1.11 KB
/
MajorityElementII.java
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
public class MajorityElementII{
public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(nums != null && nums.length > 0){
// for each vote down, three distinct numbers are removed.
// thus, if a majority element exists, it must remain in the end
int can1 = 0, can2 = 1, count1 = 0, count2 = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == can1)
count1 ++;
else if(nums[i] == can2)
count2 ++;
else if(count1 == 0){
count1 = 1;
can1 = nums[i];
} else if(count2 == 0){
count2 = 1;
can2 = nums[i];
} else {
count1 --;
count2 --;
}
}
count1 = 0;
count2 = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == can1)
count1 ++;
else if(nums[i] == can2)
count2 ++;
}
if(count1 > nums.length / 3) res.add(can1);
if(count2 > nums.length / 3) res.add(can2);
}
return res;
}
}