Majority Element


  • 0

    Click here to see the full article post


  • 0
    S

    Approach #6 fails for the following case where it returns 7 instead of -7
    []int{-7, 2, 3, 4, 5, 6, -7, -7, 7, 7, 7, -7}


  • 0
    S

    In fact, count must be set to 1 as follows
    if (count == 0) {
    candidate = num;
    count = 1;
    }


  • 0

    @swatisaoji1 That array does not have a majority element, so it is not a valid input for this problem.


  • 0
    A

    Another easy solution: K being a majority item means that every bit value of K is majority. We can then reconstruct K from the majority bit values.


  • -1
    Z

    [7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 6, 6, 6, 6]
    apporach #6 result is 6 not expected 7,so the approach is wrong!


  • 0

    @zpng The problem states that only arrays with a majority element will be passed as input. Your array does not have a majority element, so it is not valid input. For the version of the problem that works with arrays that may or may not have a majority element, you need to make a final linear pass over the array, verifying that the candidate is indeed a majority element.


  • -1
    U
    public int majorityElement(int[] nums) {
    

    HashMap<Integer, Integer> ht = new HashMap<>();
    int value = 0;
    for(int i : nums){
    if(ht.containsKey(i)){
    ht.put(i, 1+ht.get(i));
    if(ht.get(i)>nums.length/2){
    value=i;
    }
    }
    else{
    ht.put(i, 1);
    }
    }
    return nums.length==1 ? nums[0] : value;
    }


Log in to reply
 

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