# 前K个高频元素

描述

给定一个非空的整数数组，返回其中出现频率前 $$kk$$ 高的元素。

* 你可以假设给定的 $$kk$$ 总是合理的，且 $$1≤k≤1≤k≤$$ 数组中不相同的元素的个数。
* 你的算法的时间复杂度**必须**优于 $$O(nlog⁡n)O(nlogn)$$ ,$$nn$$ 是数组的大小。

样例

**样例 1:**

```
输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]
```

**样例 2:**

```
输入: nums = [1], k = 1输出: [1]
```

解题思路：

三种办法：

1。 List:得到频率Map 直接排序map（得到list），返回前K个

```
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        cnt = sorted(cnt.items(), key=lambda x: -x[1])
        return [a for a,b in cnt[:k]]
    

```

2. Heapq:heapq.nalargest, N远大于k时候选择

```
import heapq
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        return heapq.nlargest(k,cnt.keys(), key=cnt.get)

```

2. Map:直接用map.most\_common.

```
from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        return [a for a,b in cnt.most_common(k)]


```

先按照频率得到dict，r按照频率排序，也可以用堆，或者快排：左边长度\<k，继续递归快排，time complexity O(n), 因为每次只对一条分支递归。

````
```python
from typing import (
    List,
)

class Solution:
    """
    @param nums: the given array
    @param k: the given k
    @return: the k most frequent elements
             we will sort your return value in output
    """
    def top_k_frequent(self, nums: List[int], k: int) -> List[int]:
        # Write your code here
        return [i for i,_ in collections.Counter(nums).most_common(k)]
```
````

和上面一样对频率排序，自己实现python内置函数

````
// Some code```python
from typing import (
    List,
)

class Solution:
    """
    @param nums: the given array
    @param k: the given k
    @return: the k most frequent elements
             we will sort your return value in output
    """
    def top_k_frequent(self, nums: List[int], k: int) -> List[int]:
        # Write your code here
        freq_count = {}
        for i in nums:
            freq_count[i] = freq_count.get(i,0) + 1
        sorted_freq_count = sorted(freq_count.items(), key=lambda x:x[1], reverse=True)
        return [i for i,_ in sorted_freq_count[:k]]
```
````