描述
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.
分析
排序+哈希表，或者用堆解决。
解决方案1(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
26
27
| bool compare(pair<int, int> &a, pair<int, int> &b) {
return a.second > b.second;
}
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> result;
unordered_map<int, int> map_int_int;
vector<pair<int, int>> for_sort;
for(auto &item: nums) {
map_int_int[item]++;
}
for(auto &item: map_int_int) {
for_sort.push_back(make_pair(item.first, item.second));
}
sort(for_sort.begin(), for_sort.end(), compare);
for(int i = 0; i < k; i++) {
result.push_back(for_sort[i].first);
}
return result;
}
};
|
解决方案2（Golang）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func topKFrequent(nums []int, k int) []int {
numCountMap := map[int]int{}
var result []int
for _, num := range nums {
if _, ok := numCountMap[num]; !ok {
result = append(result, num)
}
numCountMap[num] += 1
}
sort.Slice(result, func(i, j int) bool {
return numCountMap[result[i]] > numCountMap[result[j]]
})
return result[:k]
}
|
相关问题