leetcode347
时间: 2023-08-21 14:08:23 浏览: 54
题目描述:给定一个非空整数数组,返回其中出现频率前 k 高的元素。
解题思路:首先,我们可以使用哈希表来统计每个元素出现的频率。然后,我们可以使用优先队列来维护出现频率前 k 高的元素。
具体步骤如下:
1. 创建一个哈希表,用于统计每个元素的频率。
2. 遍历整数数组,将每个元素及其对应的频率加入哈希表。
3. 创建一个优先队列,用于存储出现频率前 k 高的元素。
4. 遍历哈希表,将每个元素及其频率加入优先队列。同时,当优先队列的大小超过 k 时,弹出队首元素,以保证队列中只有频率前 k 高的元素。
5. 最后,遍历优先队列,取出其中的元素并返回结果。
以下是使用 Python 语言实现的代码:
```python
import heapq
from collections import Counter
def topKFrequent(nums, k):
# 统计每个元素的频率
counter = Counter(nums)
# 使用优先队列维护频率前 k 高的元素
pq = []
for num, freq in counter.items():
heapq.heappush(pq, (freq, num))
if len(pq) > k:
heapq.heappop(pq)
# 取出频率前 k 高的元素
result = []
while pq:
result.append(heapq.heappop(pq)[1])
return result[::-1]
# 测试示例
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(nums, k)) # 输出 [1, 2]
```
该代码的时间复杂度为 O(nlogk),其中 n 是整数数组的长度。