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 1:
Input: [3,2,3]
Output: [3]
Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]
代码
Approach #1 Boyer Moore
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ans = new ArrayList<Integer>();
if (nums == null || nums.length == 0) return ans;
int count1 = 0, count2 = 0;
int candidate1 = 0, candidate2 = 1;
for (int num: nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
else if (count1 == 0) {
candidate1 = num;
count1 = 1;
}
else if (count2 == 0) {
candidate2 = num;
count2 = 1;
}
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int num: nums) {
if (num == candidate1) count1 += 2;
else count1--;
if (num == candidate2) count2 += 2;
else count2--;
}
if (count1 > 0) ans.add(candidate1);
if (count2 > 0) ans.add(candidate2);
return ans;
}
}