347.Top K Frequent Elements === ###### tags: `Medium`,`Array`,`Hash Table`,`Heap`,`Divide and Conquer`,`Sorting` [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) ### 題目描述 Given an integer array `nums` and an integer `k`, return *the* `k` *most frequent elements*. You may return the answer in **any order**. ### 範例 **Example 1:** ``` Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] ``` **Example 2:** ``` Input: nums = [1], k = 1 Output: [1] ``` **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. ### 解答 #### Javascript ```javascript= function topKfrequent(nums, k) { const map = new Map(); for (const num of nums) { map.set(num, map.get(num) + 1 || 1); } // sort const sorted = [...map.entries()].sort((a, b) => b[1] - a[1]); const result = []; for (let i = 0; i < k; i++) { result.push(sorted[i][0]); } return result; } ``` > [name=Marsgoat][time=May 22, 2023] #### TypeScript ```typescript= function topKFrequent(nums: number[], k: number): number[] { const map = new Map<number, number>(); nums.forEach((num) => map.set(num, (map.get(num) || 0) + 1)); const sortedArr = [...map.entries()].sort((a, b) => b[1] - a[1]); // 這樣慢一點 但是可以一行 return sortedArr.slice(0, k).map((num) => num[0]); } ``` > [name=Sheep][time=May 22, 2023] #### Python ```python= class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: if len(nums) == k: return nums counter = Counter(nums) # Max heap heap = [(-freq, num) for num, freq in counter.items()] heapq.heapify(heap) ans = [] for _ in range(k): ans.append(heapq.heappop(heap)[1]) return ans ``` 看了題解發現可以縮 ```python= class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: if k == len(nums): return nums counter = Counter(nums) return heapq.nlargest(k, counter.keys(), key=counter.get) ``` TC: $O(nlogk)$ SC: $O(n)$ > [name=Ron Chen][time=Mon, May 22, 2023] ```python= class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: return [n for n, _ in Counter(nums).most_common(k)] ``` > [name=Yen-Chi Chen][time=Mon, May 22, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)