[数据结构与算法]1636 按照频率将数组升序排序——Leetcode天天刷（2022.9.19）【数组模拟哈希表+自定义排序】

1636 按照频率将数组升序排序——Leetcode天天刷（2022.9.19）【数组模拟哈希表+自定义排序】

前言

最近因为参加数模国赛，好久没打题了，今天打了一下今天的每日一题，没什么难度。

有时间就更新其他内容。

题目描述

题目传送门

感兴趣的可以玩一下，如果要复习排序算法的，正好可以练练手。

题目就是给你一个整数数组，然后根据数字出现在数组的 频数，也就是次数进行升序排序，特别的，如果频数相同，就按数字本身的 数值 降序 排序。

题目示例

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

输入：nums = [2,3,1,3,2]
输出：[1,3,3,2,2]
解释：'2' 和 '3' 频率都为 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

题解思路【哈希表+排序】

读完题目，思路就来啦。

我们可以使用一个哈希表来存储数字出现的次数，然后再利用出现的次数进行排序。

优化：由于题目提示中，数字的数值范围在-100 到 100之间，所以我们可以用一个长度为 201的数组来模拟哈希表，至于排序，我们可以用 algorithm 库中自带的 sort 函数的接口，对比较方式写一个 匿名函数 实现自定义特殊排序。

算法复杂度 and 执行效率

时间复杂度：$O(nlogn)$，主要是排序的时间。

空间复杂度：$O(1)$, 使用了一个空间为 200+ * sizeof(int) 的空间。

代码如下：

Code（C++）

#include<bits/stdc++.h>

using namespace std;

class Solution 
{
public:
	// 数组模拟哈希表 + 排序
    vector<int> frequencySort(vector<int>& nums) 
	{
		int cnt[200 + 5] = {0};		// 数组模拟哈希表，记录数字出现的个数
		int n = nums.size();
		// 遍历数组中的数字，记录出现的个数
		for(int i = 0; i < n; ++i)
		{
			cnt[nums[i] + 100]++;
		}
		// 自定义排序
		sort(nums.begin(), nums.end(), [&](const int& a, const int&b)
		{
			// 获取个数的时候记得要 哈希化得到出现次数
			// 次数相同时，数值降序
			if(cnt[a + 100] == cnt[b + 100])
			{
				return a > b;
			}
			// 否则次数升序
			return cnt[a + 100] < cnt[b + 100];
		});
		return nums;
    }
};

int main()
{
	int n;
	Solution* sol = new Solution();
	while(scanf("%d", &n) != EOF)
	{
		vector<int> nums(n);
		for(int i = 0; i < n; ++i)
		{
			scanf("%d", &nums[i]);
		}
		nums = sol->frequencySort(nums);
		for(int i = 0; i < n; ++i)
		{
			if(i)
			{
				printf(" ");
			}
			printf("%d", nums[i]);
		}
		printf("\n");
	}
	
	delete sol;
	return 0;
}