[LeetCode] #347. Top K Frequent Elements (HashMap, Medium)

[Cheolsker]

제한사항

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

아이디어

1. 해시맵 + 정렬을 이용한 풀이, 로직은 간단함 // O(NlogN)
   a. 숫자들의 빈도를 해시맵에 기록
   b. 해시맵을 배열로 변환시켜 빈도수에 따라 정렬
   c. k개 만큼 배열을 slice해서 리턴

2. 엘리먼트:빈도수 해시맵과 빈도수:엘리먼트[] 해시맵을 이용하여 문제풀이 // O(N)
   a. 해시맵에 엘리먼트의 빈도수 저장 (freqMap에 저장) // O(N)
   b. 버킷에 빈도수에 따른 엘리먼트[] 저장 (freqMap을 이용하여 buckets에 저장) // O(N)
   c. 엘리먼트 갯수(nums.length) 만큼 반복하여 빈도수에 따른 엘리먼트를 result에 저장 // O(N)

• O(N)이지만, O(NlogN)과 성능적으로 별로 차이가 안 날 수 있음