Majority Element

[kokocan12]

Problem

When an array is given, each element of array is integer, find majority element of array.
An element of array appear more than n/2 times, then that is majority element.

Solution

If we can use extra memory for saving count.
But majority element appears more than a half of length times, we don't need to use extra memory.

/**
 * [2,2,1,1,1,2,2] n=7
 *  Pick 2, 2(1) majority element is 2.
 *  Pick 2, 2(2) majority element is 2.
 *  Pick 1, 2(2) 1(1) majority element is 2.
 *  Pick 1, 2(2) 1(2) there is no majority element.
 *  Pick 1, 1(3) 2(2) majority element is 1.
 *  Pick 2, 1(3) 2(3) there is no majority element.
 *  Pick 2, 2(4) 1(3) majority element is 2.
 *  Can not find majority element without hash map when iterate once?
 *
 *  [1,2,3,2,2,2,3,3,3,2,2]
 *  Pick 1, res=1 count=1
 *  Pick 2, res=1 count=0
 *  Pick 3, res=3 count=1
 *  Pick 2, res=3 count=0
 *  Pick 2, res=2 count=1
 *  Pick 2, res=2 count=2
 *  Pick 3, res=2 count=1
 *  Pick 3, res=2 count=0
 *  Pick 3, res=3 count=1
 *  Pick 2, res=3 count=0
 *  Pick 2, res=2 count=1
 */

const majorityElement = function(nums) {
    let res = 0;
    let count = 0;
    
    for(num of nums) {
        if(count === 0) res = num;
        
        if(res === num) count+=1;
        else count-=1;
    }
    
    return res;
};