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;
    }


  • 0
    L
    This post is deleted!

  • -1
    R

    class Solution {
    public int majorityElement(int[] nums) {
    if (nums.length == 0)
    return -1;

        int majorElem = nums[0], count = 1;
        
        for (int i=1; i<nums.length; i++) {
            if (nums[i] == majorElem) {
                count++;
            } else {
                count --;
            }
            if (count == 0) {
                majorElem = nums[i];
                count = 1;
            }
        }
        
        if (count > nums.length/2)
            return majorElem;
        
        count = 0;
        
        for (int i=0; i<nums.length; i++) {
            if (nums[i] == majorElem) {
                count++;
            }
            
            if (count > nums.length/2)
                break;
        }
        
        return count > nums.length/2 ? majorElem : -1;
    }
    

    }


  • 0
    _

    Python's sort takes O(n) space. It's only sort of in-place.


  • 0
    P

    Boyce-Moore Algorithms is the one which is worth understanding in this.


  • 0
    N

    Thank you for explaining Boyer-Moore algorithm, that's very interesting. I was curious is it possible to optimize O(n) time solution to use only O(1) space. Turns out it is possible :)


Log in to reply
 

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