无脑使用unordered_map来保存数字出现次数,然后按照出现次数排序,如果出现次数相等,则数值大的排在前面。
class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int,int> cnt;
for(auto num:nums){
cnt[num]++;
}
sort(nums.begin(),nums.end(),[&](int a,int b){
return cnt[a] == cnt[b] ? a>b:cnt[a]<cnt[b];
});
return nums;
}
};
可以使用优化后的代码,这里数组由于下标不能为负,因此做了一个特殊处理。
class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
int map[201] = {0};
for(auto num:nums)
map[num+100]++;
sort(nums.begin(),nums.end(),[&](int a,int b){
return map[a+100] == map[b+100] ? a>b:map[a+100] < map[b+100];
});
return nums;
}
};
运行结果:
Runtime: 4 ms, faster than 97.46% of C++ online submissions for Sort Array by Increasing Frequency.
Memory Usage: 10.8 MB, less than 98.99% of C++ online submissions for Sort Array by Increasing Frequency.