Majority_Element.js

/*
Majority Element
https://leetcode.com/problems/majority-element/

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

Note: You should have a better solution than O(N)
*/
const assert = require('assert');

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  if(nums.length === 0)
    return -1;
  
  var candidate = nums[0];
  var proves = 1;
  
  for(var i = 1; i < nums.length; i++) {
    if(nums[i] === candidate) 
      proves++;
    else {
      proves--;
      if(proves === 0)  {
        candidate = nums[i];
        proves = 1;
      }
    }
  }
  
  return candidate;
};

var main = function() {
  test();
}

function test() {
  assert.equal(majorityElement([2,2,3]), 2);
  assert.equal(majorityElement([2,3,2]), 2);
  assert.equal(majorityElement([1,1,1,2,3,45,1,2,4,1,1]), 1);
}

module.exports.main = main