Boyer-Moore method in java


  • 0
    B
    public class Solution {
     public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
    	int count1 = -nums.length/3, count2 = -nums.length/3,count3=-nums.length/3, r1 = 0, r2 = 1, r3 = 2;
    	for(int num : nums){
    		if(num == r1){
    			count1+=1;
    		}else if(num == r2){
    			count2+=1;
    		}else if(num == r3){
    			count3+=1;
    		}else if(count1 == -nums.length/3){
    			r1 = num;
    			count1 = 1-nums.length/3;
    		}else if(count2 == -nums.length/3){
    			r2 = num;
    			count2 = 1-nums.length/3;
    		}else if(count3 == -nums.length/3){
    			r3 = num;
    			count3 = 1-nums.length/3;
    		}else{
    			count1-=1;
    			count2-=1;
    			count3-=1;
    		}
    	}
    	count1 = 0; count2= 0; count3 = 0;
    	for(int num: nums){
    		if(num == r1) count1+=1;
    		if(num == r2) count2+=1;	
    		if(num == r3) count3+=1;	
    	}
    	if(count1>nums.length/3) result.add(r1);
    	if(count2>nums.length/3) result.add(r2);
    	if(count3>nums.length/3) result.add(r3);
    	return result;
    }
    

    }


  • 2
    S

    it's n/3. so at most only two numbers could be the result. I shared mine a little shorter code.

    public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int count1 = 0, count2 =0; 
        int num1 = 0, num2 = 0; 
        for(int num: nums) {
            if(num1 == num) {
                count1++; 
            } else if(num2 == num) {
                count2++; 
            } else if(count1 == 0) {
                num1 = num; 
                count1 = 1; 
            } else if(count2 == 0) { 
                num2 = num; 
                count2 = 1; 
            } else {
                count1--; 
                count2--; 
            }
        } 
        
        int totalCount1 = 0; 
        int totalCount2 = 0; 
        for(int num: nums) {
            if(count1 > 0 && num == num1) totalCount1++; 
            if(count2 > 0 && num == num2) totalCount2++; 
        }
        
        List<Integer> result = new ArrayList<>(); 
        if(totalCount1 > nums.length/3) result.add(num1);
        if(totalCount2 > nums.length/3) result.add(num2); 
        
        return result; 
    }
    

    }


Log in to reply
 

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