Medium - Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/description/

Top K Frequent Elements - LeetCode

문제 설명

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Constraints:

• 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.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

예시

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

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

풀이

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = dict()
        for num in nums:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        
        return list(map(lambda x: x[1], sorted([[freq, num] for num, freq in d.items()], reverse=True)[:k]))

Follow up의 n log n은 sort에서 흔히 볼 수 있는 시간복잡도이다.

Loop를 돌며 전체 탐색 + hashmap에 빈도 저장 (n) + sort (n log n) == n log n이므로 뭔가 멕아리 없이 해결...