Question
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:
How many majority elements could it possibly have?
Code
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
if (nums.length == 1) {
result.add(nums[0]);
return result;
}
int n1 = nums[0], n2 = 0, c1 = 1, c2 = 0;
for (int i = 1; i < nums.length; i++) {
int n = nums[i];
if (n == n1) {
c1++;
} else if (n == n2) {
c2++;
} else if (c1 == 0) {
n1 = n;
c1++;
} else if (c2 == 0) {
n2 = n;
c2++;
} else {
c1--;
c2--;
}
}
c1 = 0;
c2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == n1) c1++;
else if (nums[i] == n2) c2++;
}
if (c1 > nums.length / 3) result.add(n1);
if (c2 > nums.length / 3) result.add(n2);
return result;
}
}
Solution
摩尔投票法。
数组中至多可能会有2个出现次数超过 ⌊ n/3 ⌋ 的众数
记变量n1, n2为候选众数； c1, c2为它们对应的出现次数
遍历数组，记当前数字为num
若num与n1或n2相同，则将其对应的出现次数加1
否则，若c1或c2为0，则将其置为1，对应的候选众数置为num
否则，将c1与c2分别减1
最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。
