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.
解法：参考编程之美129页，寻找发帖水王
代码如下：
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer>list=new ArrayList<Integer>();
if(nums==null) return list;
int len=nums.length;
if(len==0) return list;
if(len==1){
list.add(nums[0]);
return list;
}
int m1=nums[0];
int m2=0;
int c1=1;
int c2=0;
for(int i=1;i<len;i++){
if(nums[i]==m1)
c1++;
else if(nums[i]==m2)
c2++;
else if(c1==0){
m1=nums[i];
c1=1;
}else if(c2==0){
m2=nums[i];
c2=1;
}
else{
c1--;
c2--;
}
}
c1=0; c2=0;
for(int i=0;i<len;i++){
if(nums[i]==m1)
c1++;
else if(nums[i]==m2)
c2++;
}
if(m1!=m2){ //防止[0,0]情况出现，其实不加也可以，加了运行时间缩短20ms
if(c1>len/3) list.add(m1);
if(c2>len/3) list.add(m2);
}else{
list.add(m1);
}
return list;
}
}
运行结果：