title

problem link

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.

solution

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

设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率，即第 i 个桶中存储的数出现的频率为 i。把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。

class Solution {
public:
	vector<int> topKFrequent(vector<int>& nums, int k) {
		unordered_map<int, int> map1;
		for (auto n : nums) {
			map1[n]++;
		}
		vector<vector<int>> v(nums.size()+1);
		for (auto n : map1) {
			v[n.second].push_back(n.first);
		}
		vector<int> res;
		for (int i = v.size() - 1; i >= 0; i--) {
			for (int j : v[i]) {
				res.push_back(j);
				if (res.size() == k)
					return res;
			}
		}
		return res;
		
	}
};