给定一个大小为 n 的数组，找出其中所有出现超过 ? n/3 ? 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
思路：
摩尔投票法
超过n/3，那可能的众数个数为0，1，2
先假设两个值为众数，开始遍历数组
如果发现与假设的数字相同的数，则数量加一，否则数量减一
如果数量减到0，则更换为0的数为当前的数字。
原理：
相同总数加一，不同总数减一，这么相互抵消下去，剩下的最终a，b所代表的数字一定是最多的
提交的代码：
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<>();
if(nums.length==0)
{
return list;
}
int a=nums[0],b=nums[0];
int count1=0,count2=0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]==a)
{
count1++;
continue;
}
else if(nums[i]==b)
{
count2++;
continue;
}
else{
if(count1==0)
{
a = nums[i];
count1=1;
continue;
}
else if(count2==0)
{
b = nums[i];
count2=1;
continue;
}
else{
count1--;
count2--;
}
}
}
count1=0;
count2=0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]==a)
{
count1++;
}
else if(nums[i]==b)
{
count2++;
}
}
if(count1>nums.length/3)
{
list.add(a);
}
if(a!=b&&count2>nums.length/3)
{
list.add(b);
}
return list;
}
}