【2022-09-19每日一题】1636. 按照频率将数组升序排序
2022-09-19
1分钟阅读时长
2022-09-19每日一题：1636. 按照频率将数组升序排序
难度：Easy
标签：数组 、 哈希表 、 排序
给你一个整数数组 nums ，请你将数组按照每个值的频率 升序 排序。如果有多个值的频率相同，请你按照数值本身将它们 降序 排序。
请你返回排序后的数组。
示例 1：
输入：nums = [1,1,2,2,2,3] 输出：[3,1,1,2,2,2] 解释：'3' 频率为 1，'1' 频率为 2，'2' 频率为 3 。
示例 2：
输入：nums = [2,3,1,3,2] 输出：[1,3,3,2,2] 解释：'2' 和 '3' 频率都为 2 ，所以它们之间按照数值本身降序排序。
示例 3：
输入：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
方法一：模拟
func frequencySort(nums []int) []int {
mp := make(map[int]int)
for _, num := range nums {
mp[num]++
}
slice := make([][2]int, 0, len(mp))
for num, count := range mp {
slice = append(slice, [2]int{count, num})
}
sort.Slice(slice, func (i, j int) bool {
if slice[i][0] == slice[j][0] {
return slice[i][1] > slice[j][1]
} else {
return slice[i][0] < slice[j][0]
}
})
ans := make([]int, 0, len(nums))
for _, p := range slice {
for i := 0; i < p[0]; i++ {
ans = append(ans, p[1])
}
}
return ans
}
复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(n)
方法二：
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func frequencySort(nums []int) []int {
cnt := make(map[int]int)
for _, num := range nums {
cnt[num]++
}
sort.Slice(nums, func (i, j int) bool {
a, b := nums[i], nums[j]
// 先比较数出现次数升序，如果次数相同则按数的大小倒序
return cnt[a] < cnt[b] || cnt[a] == cnt[b] && a > b
})
return nums
}
复杂度分析
时间复杂度：O(nlogn)，其中 n 是数组nums 的长度。排序消耗 O(nlogn) 时间。
空间复杂度：O(n)，存储数组元素频率的哈希表消耗 O(n)空间。