JAVA O(N) SOLUTION SIMPLE AND EASY


  • 0
    A
    public int majorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        //2 4 4 1 3
        
        //Boyer Moore Vote Algorithm
        for(int i = 1; i < nums.length; i++){
            if(count == 0){
                candidate = nums[i];
                count = 1;
            }
            else{
                if(nums[i] == candidate){
                    count++;
                }
                else{
                    count--;
                }
            }
        }
        
        //
        count = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == candidate){
                count++;
            }
        }
        if(count > nums.length/2){
            return candidate;
        }
        else{
            return -1;
        }
    }

Log in to reply
 

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