LeetCode(229):Majority Element ||

Majority Element II: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.

题意：找出给定数组中出现次数多于数组长度三分之一的元素

思路：根据提示，可知这样的元素最多只能存在两个，因此根据摩尔投票法可以进行求解。

代码：

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
         int cnt1=0, cnt2 =0;
         int a=-1,b=-1;
         for(int n:nums){
             if(n==a) cnt1++;
             else if(n==b) cnt2++;
             else if(cnt1==0){
                 a= n;
                 cnt1=1;
             }else if(cnt2==0){
                 b = n ;
                 cnt2 = 1;
             }else{
                 cnt1--;
                 cnt2--;
             }
         }
         cnt1 = 0;
         cnt2 = 0;
         for(int n:nums){
             if(n==a) cnt1++;
             else if(n==b) cnt2++;
         }
         List<Integer> result=new ArrayList<Integer>();
         if(cnt1 > nums.length/3) result.add(a);
         if(cnt2 > nums.length/3) result.add(b);
         return result;
    }
}