LeetCode 169. 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.

翻譯

長度為n的陣列，找出一個出現n/2次以上的主要元素，假設陣列不會是空值，而且總是會有主要元素存在陣列中。

思路

用一個map來記錄毎一個元素出現幾次，只要有一個元素出現n/2次，這個元素就是主要元素。

解題

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var map = {};
    if(nums.length ===1) {return nums[0]}

    for(var i = 0 ; i < nums.length ; i++){
        // 第一次出現的元素，放到map    not in map, push element and set count = 1
        if(!map[nums[i]]) {
            map[nums[i]] = 1;
        } else {
            // 出現過的元素，數量增加    element exist, count++
            map[nums[i]]++;
            // 判斷這個元素出現的次數 > n/2
            if(map[nums[i]] >= nums.length/2){
                return nums[i];
            }
        }
    }
};