LeetCode 1122. 数组的相对排序
目录
题目描述
题意分析
要对 arr1 重新排序，但排序的「大小关系」不是数值本身，而是由 arr2 定义的一张自定义优先级表：凡是在 arr2 中出现过的值，按它在 arr2 里的下标先后排；没在 arr2 中出现过的值，统一排在所有已定义元素之后，并且内部按数值升序。
题目额外承诺 arr2 中的元素互不相同，且每个都在 arr1 中出现过。前半句保证了「值 → 优先级」是一个良定义的映射，不会出现同一个值有两个不同优先级；后半句保证按 arr2 顺序输出时每个值至少能取出一个，不会出现空转。
最关键的信号藏在数据范围里：
arr1.length与arr2.length都不超过 1000，而所有元素的取值范围是 0 到 1000。值域和数组长度同阶且都很小，这种「有限且已知的整数值域」几乎是在明示可以用值本身当下标，而不必依赖比较。注意 arr1 中的值是可以重复的，同一个值出现多次时它们彼此不可区分，全部连续排在一起即可，不存在稳定性问题。
边界上要考虑：arr1 中的值全部都在 arr2 里（第二段为空）；arr1 中的值全都不在 arr2 里（第一段为空，退化成普通升序）；值为 0 的元素（下标从 0 开始，计数数组不能少开这一格）；值恰好为 1000 的元素（数组长度必须是 1001 而不是 1000）。
解法：计数排序
核心思路
元素值只在
[0, 1000]内，适合用计数排序：先统计每个值在 arr1 中出现的次数，再按题目要求的顺序把频次展开。与“哈希优先级 + 比较排序”相比，这直接利用了小值域，避免O(n log n)排序和比较器分支。输出分两段。第一段遍历 arr2，按其给定顺序写出每个值的全部副本，并把对应计数减到 0；第二段从 0 到 1000 扫描计数表，把剩余值按数值升序写出。第一段已经清零的值在第二段自然被跳过，不需要额外集合。
维护不变量：
count[v]始终表示值 v 尚未写入结果的个数，写指针index等于已写元素数。本文直接把 arr1 当作输出缓冲区，不再申请同长度结果数组。正确性说明：第一段严格按 arr2 顺序输出所有受约束元素；每个值一次性写完，因此同值连续且数量不变。第二段按值从小到大输出所有剩余元素，正好满足“未出现在 arr2 中的元素升序”。每次输出都同步减少频次，所有计数最终归零，所以结果不重不漏。
解题步骤
- 创建长度 1001 的计数数组，统计 arr1 中每个值的频次。
- 令
index = 0，按 arr2 顺序逐个值展开全部频次，写回 arr1。- 从值 0 扫描到 1000，展开计数表中仍未消费的元素。
- 返回已经重排的 arr1。
对样例
arr1 = [2,3,1,3,2,4,6,7,9,2,19]、arr2 = [2,1,4,3,9,6]，第一段写出[2,2,2,1,4,3,3,9,6]，计数表只剩 7 和 19；第二段升序补成[2,2,2,1,4,3,3,9,6,7,19]。值 0 与 1000 都是合法边界，计数数组必须覆盖二者。
代码实现
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] count = new int[1001];
for (int value : arr1) {
count[value]++;
}
int index = 0;
for (int value : arr2) {
while (count[value] > 0) {
arr1[index++] = value;
count[value]--;
}
}
for (int value = 0; value < count.length; value++) {
while (count[value] > 0) {
arr1[index++] = value;
count[value]--;
}
}
return arr1;
}
}
func relativeSortArray(arr1 []int, arr2 []int) []int {
count := make([]int, 1001)
for _, value := range arr1 {
count[value]++
}
index := 0
for _, value := range arr2 {
for count[value] > 0 {
arr1[index] = value
index++
count[value]--
}
}
for value := 0; value < len(count); value++ {
for count[value] > 0 {
arr1[index] = value
index++
count[value]--
}
}
return arr1
}
复杂度分析
- 时间复杂度：
O(n + m + C)。n、m 分别是 arr1、arr2 的长度，C = 1001是值域大小；所有频次展开的总次数为 n。- 空间复杂度：
O(C)。只额外使用计数数组；在本题固定值域下也可视为O(1)。
关键点总结
- 小而连续的整数值域是计数排序的选择依据；若值域远大于数组长度，再考虑哈希表和比较排序。
- 第一段按 arr2 控制组间顺序，第二段按数值控制剩余元素顺序，两类规则不能混在一次扫描里。
- “消费频次并清零”同时完成输出和已处理标记，无需额外集合。
- arr1 本身可以复用为输出数组，计数完成后原排列已不再需要。
易错点总结
- 计数数组只开 1000 个位置：
arr1 = [1000]会访问越界；闭区间[0,1000]需要 1001 个槽位。- 展开频次时使用
if而不是while：arr1 = [2,2,2,1], arr2 = [2,1]会先只写一个 2，剩余 2 被错误放到尾部。- 写出后忘记减少计数：循环条件永远成立，写指针最终越过 arr1 末尾；Java 会数组越界，Go 会索引越界并 panic。
- 第二段从 1 开始或在 1000 前停止：
arr1 = [0,1000], arr2 = []会漏掉合法边界值。- 第二段仍按 arr1 原出现顺序写：
arr1 = [19,7], arr2 = []会得到[19,7]，而题目要求剩余元素升序为[7,19]。- 先覆盖 arr1、后统计频次：复用 arr1 作为输出的前提是计数已经完整保存了原数据；统计未结束就写回会污染后续计数。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 075. 数组的相对排序 | 简单 | 与本题同构的另一编号版本，可用来检验同一套计数模板能否脱稿默写 |
| 1365. 有多少小于当前数字的数字 | 简单 | 计数表要再做一次前缀和才能回答「有多少个更小」，多了一步累加而非直接读取 |
| 1636. 按照频率将数组升序排序 | 简单 | 排序键是频次本身且频次相同时按值降序，需要双关键字比较而不是照抄外部次序 |
| 75. 颜色分类 | 中等 | 值域只有三个且要求原地一趟完成，考察三路划分指针而非另开计数数组 |
| 347. 前 K 个高频元素 | 中等 | 值域无界必须用哈希计数，再靠桶排序或堆取前 K，考察从计数到选择的衔接 |
| 451. 根据字符出现频率排序 | 中等 | 对象是字符且要按频次降序重建字符串，考察定长字符表加桶排序的组合 |