CTF of Z2BNS
0%

按照频率将数组升序排序

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 726 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。

请你返回排序后的数组。

示例1：

1
2
3
输入：nums = [1,1,2,2,2,3]
输出：[3,1,1,2,2,2]
解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。

示例2：

1
2
3
输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。

示例3：

1
2
输入：nums = [-1,1,-6,4,5,-6,1,4,1]
输出：[5,-1,4,4,-6,-6,1,1,1]

提示：

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

使用桶排序，定义一个大小为201的bucket数组初始化为0，桶中第i个元素的值是nums中值为i的元素个数，也就是说nums数组中有多少个取值，bucket数组大小就为多少，注意-100<=nums[i]<=100,所以桶的大小是201。接下来修改sort排序规则，对nums数组按照值得频率升序、数值本身降序排序。

c++代码：(执行用时16ms，击败71.08%，内存消耗11.2M，击败92.67%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> frequencySort(vector<int>& nums) {
        //桶排序
        int bucket[201]={0};
        for(int i:nums){
            ++bucket[100+i];
        }
        //修改排序规则，第三个表达式是Lambda表达式，可以作为inline函数使用
        sort(nums.begin(), nums.end(), [=](int & a, int & b) {
            return (bucket[100+a]<bucket[100+b] || bucket[100+a]== bucket[100+b] && a>b);
        });
        return nums;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

没有官方题解，我觉得我这个应该差不多是最优解法了吧，效率还挺高的。昨天正在看《C++标准库 第二版》这本书，刚好看完Lambda表达式，今天就用上了😛，真好，以前遇到sort自定义规则排序的我都没好好看，现在已经会使用了。赶快把《C++标准库 第二版》还有《STL源码剖析》这两本书给看完，看完以后对中等题和难题也有信心了😊。

------------- THE END! THANKS! -------------