2015年11月3日星期二

Leetcode 229 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.
Solution 1: possible at most 2 candidates num1 and num2, so when iterate the array, num1 and num2 must appear more then n/3 times. Other nums not num1/2 appear less then n/3 times.
 public class Solution {  
   public List<Integer> majorityElement(int[] nums) {  
     int num1=0, num2=0, c1=0, c2=0;  
     for (int x:nums) {  
       if (c1>0 && x==num1) c1++;  
       else if (c2>0 && x==num2) c2++;  
       else if (c1==0) {  
         num1=x;  
         c1++;  
       }  
       else if (c2==0) {  
         num2=x;  
         c2++;  
       }  
       else {  
         c1--;  
         c2--;  
       }  
     }  
     c1=0;c2=0;  
     for (int x:nums) {  
       if (x==num1) c1++;  
       else if (x==num2) c2++;  
     }  
     List<Integer> res=new ArrayList<>();  
     if (c1>nums.length/3) res.add(num1);  
     if (c2>nums.length/3) res.add(num2);  
     return res;  
   }  
 }  

没有评论:

发表评论