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 (Java)

class Solution {
    public int majorityElement(int[] arr) {
        int count = 1;
        int majority = arr[0];
        // For Potential Majority Element
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == majority) {
                count++;
            } else {
                if (count > 1) {
                    count--;
                } else {
                    majority = arr[i];
                }
            }
        }
        // For Confirmation
        count = 0;
        for (int j : arr) {
            if (j == majority) {
                count++;
            }
        }
        if (count >= (arr.length / 2) + 1) {
            return majority;
        } else {
            return -1;
        }
    }
}

Solution 1 (Javascript)

/**
 * @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 (Javascript)

/**
 * @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).