Description
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Note: The algorithm should run in linear time and in O(1) space.
Example
Example 1:
1
2
| Input: [3,2,3]
Output: [3]
|
Example 2:
1
2
| Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
|
Solution
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
|
class Solution {
public List<Integer> majorityElement(int[] nums) {
if (nums == null || nums.length == 0) return new ArrayList<>();
int candidate1 = nums[0], candidate2 = nums[0];
int count1 = 0, count2 = 0;
for (int num: nums){
if (candidate1 == num)
count1++;
else if (candidate2 == num)
count2++;
else if (count1 == 0){
candidate1 = num;
count1++;
}
else if (count2 == 0){
candidate2 = num;
count2++;
}
else{
count1--;
count2--;
}
}
List<Integer> res = new ArrayList<>();
count1 = 0;
count2 = 0;
for (int num: nums){
if (candidate1 == num) count1++;
if (candidate2 == num) count2++;
}
if (count1 > nums.length / 3)
res.add(candidate1);
if (candidate1 != candidate2 && count2 > nums.length / 3)
res.add(candidate2);
return res;
}
}
|