引子
map自定义是按照键排序的，有些时候需要按照值排序，比如说这道题：347. Top K Frequent Elements。
方法
使用vector和自定义排序函数结合的方法：
1
2
3
4
5
| vector<pair<int, int>> anti_record;
for(auto iter = record.begin(); iter != record.end(); ++iter) {
anti_record.push_back(pair<int, int>(iter->first, iter->second));
}
sort(anti_record.begin(), anti_record.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
|
更清楚一些：
1
2
3
4
5
6
7
8
9
10
11
| bool comp(pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
}
...
int main(int argc, char **argv) {
vector<pair<int, int>> anti_record;
for(auto iter = record.begin(); iter != record.end(); ++iter) {
anti_record.push_back(pair<int, int>(iter->first, iter->second));
}
sort(anti_record.begin(), anti_record.end(), comp);
}
|
题解
引子中的题解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> result;
map<int, int> record;
for(int i : nums) {
record[i]++;
}
vector<pair<int, int>> anti_record;
for(auto iter = record.begin(); iter != record.end(); ++iter) {
anti_record.push_back(pair<int, int>(iter->first, iter->second));
}
sort(anti_record.begin(), anti_record.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
auto iter = anti_record.begin();
for(int i = 0; i < k; ++i) {
result.push_back((*iter++).first);
}
return result;
}
};
|
