[Algorithm] LeetCode - 229. Majority Element II, [Array, Hash, Sorting]

 

LeetCode 문제입니다.

[문제설명]

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

 

번역)

크기가 n인 정수 배열이 주어지면 ⌊ n/3 ⌋번 이상 나타나는 모든 요소를 찾습니다.

 

Topic: Array, Hash, Sorting, Counting

Level: Medium

Accepted 282,193 / Submissions 668,104

---

[제한사항]

 

• 1 <= nums.length <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

 

---

[입출력]

예시 1

Input: nums = [3,2,3]
Output: [3]

 

예시 2

Input: nums = [1]
Output: [1]

 

예시 3

Input: nums = [1,2]
Output: [1,2]

---

[문제풀이]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const majorityElement = (nums) => {
    // (1) make an object for storing key and counting key(value)
    let tmpObj = {}
    // (2) set a theshold n/3
    const threshold = nums.length/3
    
    // (3) save a key on the tmpObj. If it has a key, increase a counter. Else, set a key with init(1)
    nums.forEach(item => {
        if(tmpObj[item]) tmpObj[item]++
        else tmpObj[item] = 1
    })

	// (4) From entries(key, value), filter keys which is more than threshold.
    // Then, map just keys
    return Object.entries(tmpObj)
        .filter((item) => item[1] > threshold)
        .map(item => Number(item[0]))
};

 

Idea: 

1. nums 배열에서 받은 element를 Key로 하고 count를 value로 할 object 생성

2. threshold 계산

3. tmpObj에 nums 배열의 element가 key로 있으면 count를 1 올리고 그렇지 않다면 key로 지정함과 동시에 1로 init

4. tmpObj의 entries(key, value)중 value(counter)가 threhold보다 큰 것들을 필터링 한다. -> 그 후 key값들만 array로 Return 하도록 mapping

---

 

[Performance]