Concise JAVA solution based on Moore's Voting Algorithm


  • 27

    Explanation

    The basic idea is based on Moore's Voting Algorithm, we need two candidates with top 2 frequency. If meeting different number from the candidate, then decrease 1 from its count, or increase 1 on the opposite condition. Once count equals 0, then switch the candidate to the current number. The trick is that we need to count again for the two candidates after the first loop. Finally, output the numbers appearing more than n/3 times.

    Thanks for yanggao's smart advice!

    public List<Integer> majorityElement(int[] nums) {
    	  	ArrayList<Integer> res = new ArrayList<Integer>();
            if (nums.length==0) return res;
            
            int count[] = new int[2];        
            int x[] = new int[2];       
       
            x[0] = 0; x[1] = 1;        
            for (int i = 0; i < nums.length; i++) {
            	if (x[0] == nums[i])
            		count[0]++;
            	else if (x[1] == nums[i])
            		count[1]++;
            	else if (count[0] == 0) {
            		x[0] = nums[i];
            		count[0] = 1;
            	} else if (count[1] == 0) {
            		x[1] = nums[i];
            		count[1] = 1;
            	} else {
            		count[0]--;
            		count[1]--;        		
            	}
            }
            
            Arrays.fill(count, 0);
            for (int i : nums) {// Count again for x1, x2
        	if (i == x[0]) count[0]++;
        	else if (i == x[1]) count[1]++;
        }
        for (int j = 0; j < 2; j++) {
        	if (count[j] > nums.length/3 && !res.contains(x[j])) res.add(x[j]);
        }        
        return res;
    }
    

  • 0
    Y

    Hi, @Pixel_, I think that there is no need to have Integer for x array, and no need to initialize them as 0 and 1.

    Just this is fine;

        int x[] = new int[2];       
    

  • 0

    Haha, indeed! Thanks, buddy! @.@


  • 0
    Y

    you are welcome. I also think that "res.contains(x[j])" check is not necessary, since you always handle [0] before [1]


  • 0
    H

    Actually you don't need the last loop and you can do that in the second last loop

    for (int i : nums) {// Count again for x1, x2
    			if (i == x[0])
    				count[0]++;
    			else if (i == x[1])
    				count[1]++;
    			if(count[0] == nums.length / 3 || count[1] == nums.length / 3){
    				res.add(i);
    			}
    		}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.