Medium, 用时20分钟, 还是Boyer-Moore Majority Vote algorithm.
- 此题可扩展为k的情况
- error1, count1应设置为1
- error2, 未考虑corner case长度为1, 从而p1 = p2, list中有两个元素
- 本题思路比较巧妙, 构思时考虑corner case：
[2,2,9,9,1,3,4,5,6,7,8,2,2,2,2,2,2,9,9,9,9,9,9,9].
开始是p1,p2分别为2和9, 经过1,3,4,5,6,7,8后, p1,p2再次回到2和9。p1或p2其中一个移动时，另一个不动，从而保证出现次数大于n/3的存在于p1,p2中。
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
if(nums == null || nums.length == 0) return result;
int p1 = nums[0], p2 = nums[0];
int count1 = 0, count2 = 0;
int length = nums.length;
for(int i = 0; i < length; i++){
if(p1 == nums[i]){
count1 ++;
}
else if(p2 == nums[i]){
count2 ++;
}
//error2: count1 = 1, count2 = 1;
else if(count1 == 0){
p1 = nums[i];
count1 = 1;
}
else if(count2 == 0){
p2 = nums[i];
count2 = 1;
}
else{
count1 --;
count2 --;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i< length; i++){
if(nums[i] == p1) count1++;
if(nums[i] == p2) count2++;
}
if(count1 > length / 3) result.add(p1);
//error1:这里要加p1 != p2
if(count2 > length / 3 && p1 != p2) result.add(p2);
return result;
}
}
拓展: 用O(n)与O(1)找出array中出现频率最高的数:
