169. Majority Element

Problem

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

Solution 1

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  var map = {};
  var max = 0;
  var majorNum = 0;
  var len = nums.length;
  for (var i = 0; i < len; i++) {
    if (!map[nums[i]]) map[nums[i]] = 0;
    map[nums[i]]++;
    if (map[nums[i]] > max) {
      majorNum = nums[i];
      max = map[nums[i]];
    }
  }
  return majorNum;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

Solution 2

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  var count = 0;
  var majorNum = 0;
  var len = nums.length;
  for (var i = 0; i < len; i++) {
    if (!count) {
      majorNum = nums[i];
      count = 1;
    } else {
      count += (nums[i] === majorNum ? 1 : -1);
    }
  }
  return majorNum;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).