0%

leetcode Top K Frequent Elements

leetcode Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size. 题目地址:leetcode Top K Frequent Elements

题意:

给定一个数组,返回其出现次数最多的k个元素,要求复杂度小于O(nlogn)

思路:

首先扫一遍数组进行计数。

接着用一个长度为k 堆,存储出现次数最多的元素(堆顶的元素最小,每次和堆顶的元素比较即可)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef pair<int, int> P;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x] ++;
priority_queue<P, vector<P>, greater<P> > q;
for (auto &x : cnt) {
if (q.size() < k)
q.push(make_pair(x.second, x.first));
else {
if (q.top().first < x.second) {
q.pop();
q.push(make_pair(x.second, x.first));
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.top().second);
q.pop();
}
return ans;
}
};

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
counts = collections.Counter(nums)
heap = []
for key, cnt in counts.items():
if len(heap) < k:
heapq.heappush(heap, (cnt, key))
else:
if heap[0][0] < cnt:
heapq.heappop(heap)
heapq.heappush(heap, (cnt, key))
return [x[1] for x in heap]

 

本题是leetcode 347 Top K Frequent Elements  题解,

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~