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.
多个候选人的投票,从0开始计票, 因为每一票都要计算count
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<>();
if (nums == null || nums.length == 0) {
return list;
}
if (nums.length == 1) {
list.add(nums[0]);
return list;
}
int ans1 = 0, ans2 = 0;
int count1 = 0, count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != ans1 && nums[i] != ans2) {
if (count1 == 0) {
ans1 = nums[i];
count1++;
} else if (count2 == 0) {
ans2 = nums[i];
count2++;
} else {
count1--;
count2--;
}
} else if (nums[i] == ans1) {
count1++;
} else {
count2++;
}
}
count1 = 0;
count2 = 0;
for (int i : nums) {
if (i == ans1) {
count1++;
} else if (i == ans2) {
count2++;
}
}
if (count1 > nums.length / 3) {
list.add(ans1);
}
if (count2 > nums.length / 3) {
list.add(ans2);
}
return list;
}
原文：http://www.cnblogs.com/apanda009/p/7297492.html