Majority Element II Moore’s Voting/ QuickSort

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.

 Moore’s Voting Algorithm
同数加count，不同数抵消

  public List<Integer> majorityElement(int[] nums) {  
     List<Integer> ans = new ArrayList<>();  
     int n1 = 0,n2 = 0,c1 = 0, c2= 0, n = nums.length;  
     for(int i = 0; i < n; i++){  
       if(n1 == nums[i]){  
         n1 = nums[i];  
         c1 ++;  
       }else if(n2 == nums[i]){  
         n2 = nums[i];  
         c2 ++;  
       }else if(c1==0){  
         n1 = nums[i];  
         c1 ++;  
       }else if(c2==0){  
         n2 = nums[i];  
         c2 ++;  
       }else{  
         c1--;  
         c2--;  
       }  
     }  
     c1=0;c2=0;  
     for(int i = 0; i < nums.length;i++){  
       if(nums[i] == n1) c1++;  
       else if(nums[i] == n2) c2++;  
     }  
     if((double)c1 > n/3)  
       ans.add(n1);  
     if((double)c2 > n/3)  
       ans.add(n2);  
     return ans;  
   }  

方法2: QuickSort（3way partition）

https://discuss.leetcode.com/topic/35213/quick-select-c-solution

Let's say we have two indices m and n, so that all elements in [0 ... m-1] are less than the pivot, elements in [m...n] are equal to the pivot (two ends inclusive), [n+1 ... end] contains elements greater than the pivot. Then there are some facts:

• if n - m + 1 >= 1 + nums.size()/3, nums[m] must be added to the
  results.
• If m - 1 < 1 + nums.size()/3, we can simply abandon the left part, otherwise we have to consider it.
• if nums.size()-n < 1+nums.size()/3, the right part can be dropped, otherwise it has to be checked.

Ideally, we can drop about 1/3 of the array each time, so the running time is something like: 1 + 2/3 + (2/3)*(2/3) + ... = (1-(2/3)^k)/(1-2/3), O(n).

3-way-partition
p = nums[lt];i=lt+1;
while(i < gt){
      if(nums[i] == p) i++;
      else if(nums[i] < p){swap(nums,lt,i);i++;lt++;}
      else {swap(nums,gt,i); gt--;}
}