【leetcode】Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example, Given
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.
バケツのソートを利用して、3段階に分けて解決し、時間の代価O(n):各数の出現頻度を統計し、unordered_が存在する.map中 vector>コンテナを定義し、各周波数に対応する数をvectorの に存在させる.容器を逆順序で遍歴する、結果容器にk個の数を順次格納 .
For example, Given
[1,1,1,2,2,3] and k = 2, return [1,2] . Note:
バケツのソートを利用して、3段階に分けて解決し、時間の代価O(n):
class Solution {
public:
vector topKFrequent(vector& nums, int k)
{
unordered_map dict;
vector result;
for (auto n : nums)
++dict[n];
vector< vector > freq(nums.size() + 1);
for (auto p : dict)
freq[p.second].push_back(p.first);
for (int i = freq.size() - 1; i >= 0 && result.size() < k; --i)
{
for (auto n : freq[i])
{
result.push_back(n);
if (result.size() == k)
break;
}
}
return result;
}
};