[Leetcode] 169. Majority Element - JS

https://leetcode.com/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
- 정수 배열 nums 속 다수인 요소를 반환하라.
- 다수인 요소는 n / 2 이상 등장하는 요소이다.

제한사항
--------------------
- n == nums.length
- 1 <= n <= 5 * 10^4
- -10^9 <= nums[i] <= 10^9

 

 

2. 접근 방법

해쉬 테이블 사용하여 갯수를 측정하고
majority 변수에 해쉬 테이블에서 갯수를 비교하여 더 많은 요소를 할당한다.

 

 

풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    const hash = {};
    let majority = nums[0];
    for (let num of nums) {
         hash[num] = (hash[num] || 0) + 1;

        if (hash[num] > hash[majority]) {
            majority = num;
        }
    }
    return majority
};

 

해쉬 테이블로 갯수를 측정하고, 해쉬 테이블에 등록된 현재 요소의 갯수와 majority 요소의 갯수 중 더 많은 요소를 할당한다.

 

 

다른 사람 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let freq = {}
    for(i of nums){
        freq[i] = (freq[i] || 0) +1
        if(freq[i]>nums.length/2) return i
    }
};

 

해쉬 테이블에 요소 갯수를 등록하는 것 까진 비슷하지만, majority 변수를 생성하는 것 대신

문제의 조건에서 주어졌듯이 요소 갯수가 n / 2를 초과하는 조건을 만족하는 요소를 반환하여 해결했다.

 

이 방법이 더 문제 조건에 충실하고 깔끔한 방법인 것 같다.