Relative Sort Array 深度解析leetcode 仓库中五种解法暴力、哈希、计数排序、自定义比较器的完整实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇基于 leetcode 仓库中的算法讲解文档 relative-sort-array.md围绕「相对数组排序」问题LeetCode 1122系统展开先明确问题模型与前置知识再依次给出暴力扫描、频次哈希、最优哈希、计数排序、自定义比较器五种解法的完整直觉、算法步骤、多语言实现与复杂度分析最后总结易错点。读完后你能掌握该问题的多种实现路径、各方案的取舍依据以及每种解法在 Python / Java / C / Go 等语言中的可运行代码。问题模型与前置知识问题的核心规则是给定两个数组arr1和arr2其中arr2是arr1中一组不同元素的相对顺序定义。要求重排arr1使其中的元素优先按照arr2给出的顺序排列arr2中不存在的元素则按升序追加到结果末尾。在动手之前文档的 Prerequisites 部分建议先掌握三类基础哈希表Hash Maps用于统计元素频次并把元素映射到它们的排序优先级排序Sorting理解内置排序函数与自定义比较器custom comparator计数排序Counting Sort当值域有界时可实现线性时间的排序。仓库将各语言实现统一按目录组织python/、java/、cpp/、go/ 等本问题各解法的多语言参考实现集中收录在 relative-sort-array.md 中下文按文档原文的五个方案顺序逐一深入。方案一暴力扫描Brute Force直觉最直接的思路是按arr2的顺序逐个处理对arr2中的每个值扫描一遍arr1找出所有匹配项并标记为已用。处理完arr2全部元素后arr1中剩余的未标记元素按升序追加到结果末尾。这个方案直接模仿题目要求先按arr2指定的顺序放置元素再把剩下的按排序顺序追加。算法步骤创建空的结果列表res遍历arr2中的每个数字扫描arr1找出该数字的所有出现位置将每个出现位置的值追加到res并把arr1中该位置标记为已用置为-1对修改后的arr1排序-1标记值会排到最前面将所有非-1的未标记元素追加到res返回res。参考实现Pythonclass Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]: res [] for num2 in arr2: for i, num1 in enumerate(arr1): if num1 num2: res.append(num1) arr1[i] -1 arr1.sort() for i in range(len(res), len(arr1)): res.append(arr1[i]) return resJavapublic class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { ListInteger res new ArrayList(); for (int num2 : arr2) { for (int i 0; i arr1.length; i) { if (arr1[i] num2) { res.add(arr1[i]); arr1[i] -1; } } } Arrays.sort(arr1); for (int i res.size(); i arr1.length; i) { res.add(arr1[i]); } return res.stream().mapToInt(i - i).toArray(); } }Cclass Solution { public: vectorint relativeSortArray(vectorint arr1, vectorint arr2) { vectorint res; for (int num2 : arr2) { for (int i 0; i arr1.size(); i) { if (arr1[i] num2) { res.push_back(arr1[i]); arr1[i] -1; } } } sort(arr1.begin(), arr1.end()); for (int i res.size(); i arr1.size(); i) { res.push_back(arr1[i]); } return res; } };Gofunc relativeSortArray(arr1 []int, arr2 []int) []int { res : []int{} for _, num2 : range arr2 { for i : 0; i len(arr1); i { if arr1[i] num2 { res append(res, arr1[i]) arr1[i] -1 } } } sort.Ints(arr1) for i : len(res); i len(arr1); i { res append(res, arr1[i]) } return res }时间与空间复杂度时间复杂度O(m * n n log n)空间复杂度排序取决于算法本身为O(1)或O(n)另外结果列表需要O(n)空间。其中n为arr1的长度m为arr2的长度。方案二频次哈希表Hash Map直觉与其对arr2的每个元素反复扫描arr1不如先用哈希表统计arr1中每个元素的频次这样在构造结果时就是O(1)查表。同时用一个集合set快速判断arr1中哪些元素不在arr2里——这些「多出来的」元素单独收集、排序后追加到结果末尾。算法步骤由arr2构建集合实现O(1)的成员判断用哈希表统计arr1中每个元素的频次统计的同时把不在arr2中的元素收集到一个单独的列表里对该「剩余元素」列表排序构造结果按arr2的顺序每个数字按其出现次数追加到结果中把排好序的剩余元素追加到结果末尾返回结果。参考实现Pythonclass Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]: arr2_set set(arr2) arr1_count defaultdict(int) end [] for num in arr1: if num not in arr2_set: end.append(num) arr1_count[num] 1 end.sort() res [] for num in arr2: for _ in range(arr1_count[num]): res.append(num) return res endJavapublic class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { SetInteger arr2Set new HashSet(); for (int num : arr2) arr2Set.add(num); MapInteger, Integer count new HashMap(); ListInteger end new ArrayList(); for (int num : arr1) { if (!arr2Set.contains(num)) end.add(num); count.put(num, count.getOrDefault(num, 0) 1); } Collections.sort(end); ListInteger res new ArrayList(); for (int num : arr2) { int freq count.get(num); for (int i 0; i freq; i) res.add(num); } res.addAll(end); return res.stream().mapToInt(i - i).toArray(); } }Cclass Solution { public: vectorint relativeSortArray(vectorint arr1, vectorint arr2) { unordered_setint arr2Set(arr2.begin(), arr2.end()); unordered_mapint, int count; vectorint end; for (int num : arr1) { if (!arr2Set.count(num)) end.push_back(num); count[num]; } sort(end.begin(), end.end()); vectorint res; for (int num : arr2) { for (int i 0; i count[num]; i) { res.push_back(num); } } res.insert(res.end(), end.begin(), end.end()); return res; } };Gofunc relativeSortArray(arr1 []int, arr2 []int) []int { arr2Set : make(map[int]bool) for _, num : range arr2 { arr2Set[num] true } count : make(map[int]int) var end []int for _, num : range arr1 { if !arr2Set[num] { end append(end, num) } count[num] } sort.Ints(end) var res []int for _, num : range arr2 { for i : 0; i count[num]; i { res append(res, num) } } return append(res, end...) }时间与空间复杂度时间复杂度O(n m n log n)空间复杂度O(n)。其中n为arr1的长度m为arr2的长度。相比暴力法这里把「对arr2每个元素全扫一遍arr1」的m * n项替换为一次线性计数加哈希查表是关键的优化点。方案三频次哈希表最优版Hash Map Optimal直觉这是方案二的更精炼版本。不再单独维护一个「剩余元素」列表而是先统计全部元素的频次然后分两阶段处理结果第一阶段按arr2的顺序输出第二阶段按剩余 key 的升序输出。核心技巧是——在按arr2处理每个 key 时顺手把它从哈希表中删除最后表中剩下的 key 恰好就是不在arr2中的元素对其排序后按频次追加即可完成结果。算法步骤用哈希表统计arr1中每个元素的频次构造结果遍历arr2按频次把对应数字追加到结果然后从哈希表中删除该 key取出哈希表中剩余的 key即不在arr2中的元素并排序按排序后的顺序把每个剩余 key 按其频次追加到结果返回结果。参考实现Pythonpop一步完成「取频次 删 key」class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]: count {} for num in arr1: count[num] count.get(num, 0) 1 res [] for num in arr2: res [num] * count.pop(num) for num in sorted(count): res [num] * count[num] return resJavaremove同时返回频次并删除public class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { MapInteger, Integer count new HashMap(); for (int num : arr1) { count.put(num, count.getOrDefault(num, 0) 1); } ListInteger res new ArrayList(); for (int num : arr2) { int freq count.remove(num); for (int i 0; i freq; i) { res.add(num); } } ListInteger remaining new ArrayList(count.keySet()); Collections.sort(remaining); for (int num : remaining) { int freq count.get(num); for (int i 0; i freq; i) { res.add(num); } } return res.stream().mapToInt(i - i).toArray(); } }Cclass Solution { public: vectorint relativeSortArray(vectorint arr1, vectorint arr2) { unordered_mapint, int count; for (int num : arr1) { count[num]; } vectorint res; for (int num : arr2) { for (int i 0; i count[num]; i) { res.push_back(num); } count.erase(num); } vectorint remaining; for (auto [num, freq] : count) { for (int i 0; i freq; i) { remaining.push_back(num); } } sort(remaining.begin(), remaining.end()); res.insert(res.end(), remaining.begin(), remaining.end()); return res; } };Gofunc relativeSortArray(arr1 []int, arr2 []int) []int { count : make(map[int]int) for _, num : range arr1 { count[num] } var res []int for _, num : range arr2 { for i : 0; i count[num]; i { res append(res, num) } delete(count, num) } var remaining []int for num : range count { remaining append(remaining, num) } sort.Ints(remaining) for _, num : range remaining { for i : 0; i count[num]; i { res append(res, num) } } return res }时间与空间复杂度时间复杂度O(n m n log n)空间复杂度O(n)。其中n为arr1的长度m为arr2的长度。相比方案二它消除了显式的「剩余元素」收集和成员判断集合逻辑上只维护一个哈希表代码更紧凑也更不易出错。方案四计数排序Counting Sort直觉当arr1的取值范围有界且相对较小时计数排序非常高效创建一个数组下标表示数值内容表示出现次数。这个方案的妙处在于——「剩余元素」天然有序只需从下标 0 遍历到最大值未在处理阶段被清零的计数项自动按升序被收集。arr2中出现的元素先被处理处理后计数清零之后整体扫描计数数组即可补齐其余元素。算法步骤找出arr1的最大值确定计数数组的大小创建计数数组并填入arr1中各元素的频次构造结果按arr2的顺序把每个数字按其计数追加并将其计数置为0从0遍历到最大值对每个计数非零的下标按计数把该值追加到结果返回结果。参考实现Pythonclass Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]: max_val max(arr1) count [0] * (max_val 1) for num in arr1: count[num] 1 res [] for num in arr2: res [num] * count[num] count[num] 0 for num in range(len(count)): res [num] * count[num] return resJavapublic class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { int max 0; for (int num : arr1) max Math.max(max, num); int[] count new int[max 1]; for (int num : arr1) count[num]; ListInteger res new ArrayList(); for (int num : arr2) { while (count[num]-- 0) res.add(num); } for (int num 0; num count.length; num) { while (count[num]-- 0) res.add(num); } return res.stream().mapToInt(i - i).toArray(); } }Cclass Solution { public: vectorint relativeSortArray(vectorint arr1, vectorint arr2) { int max_val *max_element(arr1.begin(), arr1.end()); vectorint count(max_val 1, 0); for (int num : arr1) count[num]; vectorint res; for (int num : arr2) { while (count[num]-- 0) res.push_back(num); } for (int num 0; num max_val; num) { while (count[num]-- 0) res.push_back(num); } return res; } };Gofunc relativeSortArray(arr1 []int, arr2 []int) []int { maxVal : 0 for _, num : range arr1 { if num maxVal { maxVal num } } count : make([]int, maxVal1) for _, num : range arr1 { count[num] } var res []int for _, num : range arr2 { for count[num] 0 { res append(res, num) count[num]-- } } for num : 0; num maxVal; num { for count[num] 0 { res append(res, num) count[num]-- } } return res }时间与空间复杂度时间复杂度O(n m M)其中M是arr1的最大值空间复杂度额外O(M)的计数数组另外结果列表需要O(n)空间。其中n为arr1的长度m为arr2的长度。从源码结构看该方案把排序问题彻底转化为线性扫描只要M与n同量级时间复杂度就优于所有基于比较排序的O(n log n)方案但若M远大于n值域稀疏计数数组的开销会反超哈希方案选型时应结合值域规模判断。方案五自定义比较器排序Custom Sort直觉不手动摆放元素而是借助内置排序算法加自定义比较器完成。关键洞察是给每个元素分配一个基于其在arr2中位置的「优先级」——arr2中的元素其优先级就是它在arr2中的下标下标越小结果中越靠前不在arr2中的元素分配一个较大的优先级文档采用1000 元素值使它们整体排在所有arr2元素之后且彼此之间按实际数值升序排列。算法步骤建立哈希表把arr2中每个元素映射到它的下标定义自定义比较器对每个元素其排序键为「在arr2中的下标若存在否则为1000 元素值」用该比较器对arr1排序返回排序后的数组。这个方案非常简洁利用arr2下标的天然有序性决定最终顺序一次排序调用即可得到答案。参考实现Pythonsorted key 函数最精简的写法class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) - List[int]: index {num: i for i, num in enumerate(arr2)} return sorted(arr1, keylambda x: (index.get(x, 1000 x)))Java需要装箱为Integer[]才能使用比较器public class Solution { public int[] relativeSortArray(int[] arr1, int[] arr2) { MapInteger, Integer index new HashMap(); for (int i 0; i arr2.length; i) { index.put(arr2[i], i); } Integer[] boxed Arrays.stream(arr1).boxed().toArray(Integer[]::new); Arrays.sort(boxed, (a, b) - { int ia index.getOrDefault(a, 1000 a); int ib index.getOrDefault(b, 1000 b); return Integer.compare(ia, ib); }); return Arrays.stream(boxed).mapToInt(i - i).toArray(); } }Cclass Solution { public: vectorint relativeSortArray(vectorint arr1, vectorint arr2) { unordered_mapint, int index; for (int i 0; i arr2.size(); i) { index[arr2[i]] i; } sort(arr1.begin(), arr1.end(), { int ia index.count(a) ? index[a] : 1000 a; int ib index.count(b) ? index[b] : 1000 b; return ia ib; }); return arr1; } };Gosort.Slice配自定义断言函数func relativeSortArray(arr1 []int, arr2 []int) []int { index : make(map[int]int) for i, num : range arr2 { index[num] i } sort.Slice(arr1, func(i, j int) bool { ia, okA : index[arr1[i]] ib, okB : index[arr1[j]] if !okA { ia 1000 arr1[i] } if !okB { ib 1000 arr1[j] } return ia ib }) return arr1 }时间与空间复杂度时间复杂度O(n m n log n)空间复杂度额外O(m)优先级映射结果列表需要O(n)空间。其中n为arr1的长度m为arr2的长度。需要留意1000 x这个偏移量的隐含前提arr2的长度不超过 1000 且元素值本身不会与下标区间冲突在 LeetCode 该题的约束下成立。从源码结构看这正是「把多维偏序压成一维排序键」的典型技巧适合在支持 key-based 排序的语言如 Python 的sorted(key...)中使用。五种方案横向对比以n为arr1长度、m为arr2长度、M为arr1最大值为基准五种方案的性能特征如下方案时间复杂度额外空间适用场景暴力扫描O(m*n n log n)O(1)~O(n)取决于排序算法教学对照直观理解题意频次哈希O(n m n log n)O(n)通用场景显式分离剩余元素最优哈希删除式O(n m n log n)O(n)通用场景代码最紧凑计数排序O(n m M)O(M)值域有界且紧凑追求线性时间自定义比较器O(n m n log n)O(m)支持 key 排序的语言一次排序出结果选型的经验法则是值域信息明确且M不大时优先考虑计数排序值域未知或稀疏时哈希方案最稳妥追求代码简洁且语言支持排序 key 时自定义比较器是首选。常见陷阱Common Pitfalls文档最后专门总结了两个高频错误值得对照自查忘记对不在arr2中的元素排序按arr2的相对顺序放好所有元素后剩余元素必须按升序排序再追加到结果末尾。常见错误是把这些剩余元素按它们在arr1中的原始顺序或遇到的顺序直接追加而漏掉了排序步骤。迭代arr1时修改它暴力方案用标记例如置-1处理已用元素时边迭代边修改数组很容易导致元素被跳过或索引错乱。更稳妥的做法是使用哈希表等独立数据结构来追踪频次从根本上避开对原数组的就地修改。小结本篇以 leetcode 仓库的 relative-sort-array.md 为主体完整覆盖了「相对数组排序」问题的五种解法从暴力扫描建立直觉到频次哈希与删除式最优哈希消除重复扫描再到计数排序实现线性时间与自定义比较器的一次性排序。所有方案均给出了 Python、Java、C、Go 四种语言的完整实现原文档中另收录了 JavaScript、TypeScript、C#、Kotlin、Swift、Rust 的实现可直接在同一文档中查阅对照。掌握这些方案的取舍逻辑与易错点后可以进一步迁移到仓库中其他基于频次统计、计数排序与自定义比较器的排序类问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考