Day 22 - LeetCode 169. Majority Element

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 次, 就是主要元素
另一種做法, 因為題目有假設陣列不是空值, 而且總是會有主要元素
所以可以直接排序, 取列陣中間那個為答案

詳細參閱

https://discuss.leetcode.com/topic/82412/intuitive-javascript-solution

---

Code

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

    let map = {};

    for ( let i = 0; i < nums.length; i++ ) {
        //空的就寫入
        if ( !map[nums[i]] ) {
            map[nums[i]] = 1;
        } else {
            //已有值就+1
            map[nums[i]]++;
            if ( map[nums[i]] >= nums.length / 2 ) {
                return nums[i];
            }
        }
    }
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    // sort the array and the middle is the majority
    nums.sort((a,b) => a - b);
    return nums[Math.floor(nums.length/2)];
}; 

Run