347. Top K Frequent Elements - medium
문제
Given a non-empty array of integers, return the k most frequent elements.
제한사항
- 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.
- It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
- You can return the answer in any orde
입출력 예
1
2
3
4
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1
2
3
4
Example 2:
Input: nums = [1], k = 1
Output: [1]
풀이
- Hash
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
26
27
28
bool compare(std::pair<int,int> a, std::pair<int,int> b){
if(a.second == b.second)
return a.first < b.first;
else
return a.second > b.second;
}
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
std::vector<int> result;
std::vector<std::pair<int,int>> item;
std::unordered_map<int, int> m;
for(auto &i : nums)
++m[i];
for(auto &[key, val] : m)
item.push_back(std::make_pair(key, val));
std::sort(item.begin(), item.end(), compare);
for(auto i = 0 ; i < k ; ++i)
result.push_back(item[i].first);
return result;
}
};