前K个高频元素

https://www.lintcode.com/problem/1281/description?utm_source=sc-libao-ql

描述

给定一个非空的整数数组，返回其中出现频率前 $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]]
    

1. 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)

1. 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]]
```