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++

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

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/