> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2024/qiankge-gao-pin-yuan-su.md).

# 前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]]
```
````


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/qiankge-gao-pin-yuan-su.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.