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)