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.
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return res;
}
int n1 = 0, n2 = 0;
int count1 = 0, count2 = 0;
for (int s : nums) {
if (count1 == 0) {
n1 = s;
count1++;
} else if (count2 == 0 && n1 != s) {
n2 = s;
count2++;
} else if (s == n1) {
count1++;
} else if (s == n2) {
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int s : nums) {
if (s == n1) {
count1++;
} else if (s == n2) {
count2++;
}
}
if (count1 > nums.length / 3) {
res.add(n1);
}
if (count2 > nums.length / 3) {
res.add(n2);
}
return res;
}
}
没有评论:
发表评论