A naive Java solution using O(1) extra space (thus must be O(n) time)


  • 2
    W

    public class Solution {

    public int majorityElement(int[] nums) {
        int majority = nums[0];
        int cnt = 1;
        for(int i = 1; i < nums.length; ++i){
            if(cnt == 0){
                majority = nums[i];
                ++cnt;
            }
            else{
                if(majority == nums[i])
                    ++cnt;
                else
                    --cnt;
            }
        }
        return majority;
    }
    

    }


  • -2
    L

    you answer is not right even it passes the OJ. Try[1,2,3,4,5,6,7,7], it will give answer 7 which is not right.
    It is half Boyer-Moore Implementation, it only makes sure majority has the max occurrence but not greater than ⌊ n/2 ⌋
    you need to loop through the array again to check if majority is actually the answer.


  • 0
    W

    "You may assume that the array is non-empty and the majority element always exist in the array."-- Please read the description again.


Log in to reply
 

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