给定一个大小为 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;

    }

}