计数排序（API / 哈希映射 / 定长列表实现）+ 自定义排序，3 解法求解《1636. 按照频率将数组升序排序》
例题
1636. 按照频率将数组升序排序
给你一个整数数组 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
答案
自定义排序 · 计数 API
var frequencySort = function(nums) { // Object 实现
const h = _.countBy(nums)
nums.sort((a, b) => h[a] - h[b] || b - a)
return nums
};class Solution {
function frequencySort($nums) {
$h = array_count_values($nums);
usort($nums, fn($a, $b) => $h[$a] === $h[$b] ? $a < $b : $h[$a] > $h[$b]);
return $nums;
}
}public class Solution {
public int[] FrequencySort(int[] nums) {
Dictionary<int, int> h = nums.GroupBy(x => x).ToDictionary(x => x.Key, x => x.Count());
Array.Sort(nums, (a, b) => h[a] == h[b] ? b - a : h[a] - h[b]);
return nums;
}
}class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
sort(nums.begin(), nums.end(), [nums](const int a, const int b) -> bool {
int cntA = count(nums.begin(), nums.end(), a);
int cntB = count(nums.begin(), nums.end(), b);
if (cntA == cntB) return a > b;
return cntA < cntB;
});
return nums;
}
};class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
h = Counter(nums)
nums.sort(key = lambda v: (h[v], -v))
return nums自定义排序 · 定长列表
var frequencySort = function(nums) {
const n = nums.length, h = new Uint8Array(201)
for (let i = 0; i < n; i++) h[nums[i] + 100]++
nums.sort((a, b) => h[a + 100] - h[b + 100] || b - a)
return nums
};function frequencySort(nums: number[]): number[] {
const n = nums.length, h = new Uint8Array(201)
for (let i = 0; i < n; i++) h[nums[i] + 100]++
nums.sort((a, b) => h[a + 100] - h[b + 100] || b - a)
return nums
};class Solution {
function frequencySort($nums) {
$h = array_fill(0, 201, 0);
foreach ($nums as $num) $h[$num + 100]++;
usort($nums, fn($a, $b) => $h[$a + 100] === $h[$b + 100] ? $a < $b : $h[$a + 100] > $h[$b + 100]);
return $nums;
}
}func frequencySort(nums []int) []int {
h := make([]int, 201)
for _, n := range nums {
h[n + 100]++
}
sort.Slice(nums, func(i, j int) bool {
if h[nums[i] + 100] == h[nums[j] + 100] {
return nums[i] > nums[j]
}
return h[nums[i] + 100] < h[nums[j] + 100]
})
return nums
}class Solution {
public int[] frequencySort(int[] nums) {
int[] h = new int[201];
for (int num : nums) h[num + 100]++;
Integer[] numsBoxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(numsBoxed, (a, b) -> h[a + 100] == h[b + 100] ? b - a : h[a + 100] - h[b + 100]);
return Arrays.stream(numsBoxed).mapToInt(v -> v).toArray();
}
}public class Solution {
public int[] FrequencySort(int[] nums) {
int[] h = new int[201];
foreach (int num in nums) {
h[num + 100]++;
}
Array.Sort(nums, (a, b) => h[a + 100] == h[b + 100] ? b - a : h[a + 100] - h[b + 100]);
return nums;
}
}int* h;
static inline int cmp(const void *pa, const void *pb) {
int a = *(int*) pa + 100, b = *(int*) pb + 100;
return h[a] == h[b] ? b - a : h[a] - h[b];
}
int* frequencySort(int* nums, int numsSize, int* returnSize){
h = malloc(sizeof(int) * 201);
memset(h, 0, sizeof(int) * 201); // 可省略
for (int i = 0; i < numsSize; i++) h[nums[i] + 100]++;
qsort(nums, numsSize, sizeof(int), cmp);
*returnSize = numsSize;
return nums;
}class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
vector<int> h(201, 0);
for (int num : nums) h[num + 100]++;
sort(nums.begin(), nums.end(), [&h](const int a, const int b) -> bool {
return h[a + 100] == h[b + 100] ? a > b : h[a + 100] < h[b + 100];
});
return nums;
}
};class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
h = [0] * 201
for num in nums: h[num + 100] += 1
nums.sort(key = lambda v: (h[v + 100], -v))
return nums自定义排序 · 哈希映射
var frequencySort = function(nums) { // Object 实现
const n = nums.length, h = Object.create(null)
for (let i = 0; i < n; i++) h[nums[i]] = (h[nums[i]] || 0) + 1
nums.sort((a, b) => h[a] - h[b] || b - a)
return nums
};function frequencySort(nums: number[]): number[] { // Map 实现
const n = nums.length, h = new Map<number, number>()
for (let i = 0; i < n; i++) h.set(nums[i], (h.get(nums[i]) || 0) + 1)
nums.sort((a, b) => h.get(a) - h.get(b) || b - a)
return nums
};class Solution {
function frequencySort($nums) {
$h = [];
foreach ($nums as $num) $h[$num] = ($h[$num] ?? 0) + 1;
usort($nums, fn($a, $b) => $h[$a] === $h[$b] ? $a < $b : $h[$a] > $h[$b]);
return $nums;
}
}func frequencySort(nums []int) []int {
h := make(map[int]int)
for _, n := range nums {
h[n]++
}
sort.Slice(nums, func(i, j int) bool {
if h[nums[i]] == h[nums[j]] {
return nums[i] > nums[j]
}
return h[nums[i]] < h[nums[j]]
})
return nums
}class Solution {
public int[] frequencySort(int[] nums) {
Map<Integer, Integer> h = new HashMap<Integer, Integer>();
for (int num : nums) h.put(num, h.getOrDefault(num, 0) + 1);
Integer[] numsBoxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(numsBoxed, (a, b) -> h.get(a) == h.get(b) ? b - a : h.get(a) - h.get(b));
return Arrays.stream(numsBoxed).mapToInt(v -> v).toArray();
}
}public class Solution {
public int[] FrequencySort(int[] nums) {
Dictionary<int, int> h = new Dictionary<int, int>();
foreach (int num in nums) {
if (h.ContainsKey(num) == false) h.Add(num, 1);
else h[num]++;
}
Array.Sort(nums, (a, b) => h[a] == h[b] ? b - a : h[a] - h[b]);
return nums;
}
}typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
HashItem* h;
static inline int cmp(const void *pa, const void *pb) {
int a = *(int*) pa, b = *(int*) pb;
HashItem* pEntryA = NULL;
HASH_FIND_INT(h, &a, pEntryA);
HashItem* pEntryB = NULL;
HASH_FIND_INT(h, &b, pEntryB);
return pEntryA->val == pEntryB->val ? b - a : pEntryA->val - pEntryB->val;
}
int* frequencySort(int* nums, int numsSize, int* returnSize){
for (int i = 0; i < numsSize; i++) {
HashItem* pEntry = NULL;
HASH_FIND_INT(h, &nums[i], pEntry);
if (pEntry == NULL) {
pEntry = malloc(sizeof(HashItem));
pEntry->key = nums[i];
pEntry->val = 1;
HASH_ADD_INT(h, key, pEntry);
} else {
pEntry->val++;
}
}
qsort(nums, numsSize, sizeof(int), cmp);
HashItem* cur, * tmp;
HASH_ITER(hh, h, cur, tmp) {
HASH_DEL(h, cur);
free(cur);
};
*returnSize = numsSize;
return nums;
}class Solution {
public:
vector<int> frequencySort(vector<int>& nums) {
unordered_map<int, int> h;
for (int num : nums) h[num]++;
sort(nums.begin(), nums.end(), [&h](const int a, const int b) -> bool {
return h[a] == h[b] ? a > b : h[a] < h[b];
});
return nums;
}
};class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
h = dict()
for num in nums: h[num] = h.get(num, 0) + 1
nums.sort(key = lambda v: (h[v], -v))
return nums