LeetCode-Go 题解 | 1122. Relative Sort Array相对排序数组的哈希计数与桶排序 Go 实现【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 1122. Relative Sort Array 题解文档 为核心深入讲解「相对排序」这一经典数组题目的两种 Go 实现——基于 map 的哈希计数法与基于定长桶的桶排序法并对照 LeetCode-Go 仓库中的源码与测试用例帮助读者掌握此类「按外部顺序重排 剩余元素升序」问题的通用解法与复杂度权衡。题目Relative Sort ArrayGiven two arraysarr1andarr2, the elements ofarr2are distinct, and all elements inarr2are also inarr1.Sort the elements ofarr1such that the relative ordering of items inarr1are the same as inarr2. Elements that dont appear inarr2should be placed at the end ofarr1inascendingorder.示例Input: arr1 [2,3,1,3,2,4,6,7,9,2,19], arr2 [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19]题目给出两个数组arr1与arr2arr2中的元素互不相同且arr2的每个元素都必然出现在arr1中。要求对arr1排序使得arr1中元素之间的相对顺序与arr2中元素出现的相对顺序保持一致未在arr2中出现过的元素则需要按升序排在arr1的末尾。以示例为例arr2的顺序是2 → 1 → 4 → 3 → 9 → 6因此arr1中所有2共 3 个排在最前接着是1、4、3、9、6按序排列而7与19不在arr2中按升序追加在末尾得到[2,2,2,1,4,3,3,9,6,7,19]。题目大意给你两个数组arr1和arr2arr2中的元素各不相同arr2中的每个元素都出现在arr1中。对arr1中的元素进行排序使arr1中项的相对顺序和arr2中的相对顺序相同未在arr2中出现过的元素按照升序放在arr1的末尾。约束条件约束数值数组长度arr1.length, arr2.length 1000元素取值范围0 arr1[i], arr2[i] 1000arr2唯一性每个arr2[i]各不相同包含关系每个arr2[i]都出现在arr1中这三条约束直接决定了算法选型数组长度不超过 1000元素值被限制在[0, 1000]的整数区间内为 O(n) 级别的计数排序 / 桶排序提供了天然的可行性。解题思路本题在 LeetCode-Go 仓库中收录了两种解法分别对应 题解文档 中提到的两条思路暴力模拟哈希计数先把arr1中所有元素统计频次放入 map然后按照arr2的顺序依次输出接着把剩余元素排序后接在末尾桶排序思想由于题目限定了arr1的大小为 1000数量级很小可以用 1001 个桶装下所有可能的值把数放进桶里后天然有序。接下来的做法与第一种思路类似按频次输出arr2中的元素按其在arr2中的顺序输出其余元素则按桶的下标即数值本身从小到大依次输出。两种思路的完整实现位于 1122. Relative Sort Array.go 中下文逐一剖析。解法一定长桶计数O(n) 级别有序输出源码实现如下对应 1122. Relative Sort Array.go// 解法一 桶排序时间复杂度 O(n^2) func relativeSortArray(A, B []int) []int { count : [1001]int{} for _, a : range A { count[a] } res : make([]int, 0, len(A)) for _, b : range B { for count[b] 0 { res append(res, b) count[b]-- } } for i : 0; i 1001; i { for count[i] 0 { res append(res, i) count[i]-- } } return res }执行流程分为三个清晰的阶段统计频次遍历arr1将每个元素值作为下标累加到定长数组count [1001]int中。由于约束保证元素值在[0, 1000]内直接以值作下标即可无需哈希按arr2顺序输出遍历arr2对每个元素b将count[b]个b依次追加到结果中并同步递减计数。这里巧妙地复用了arr2本身作为「输出顺序表」剩余元素升序输出再次遍历 1001 个桶下标天然就是元素值从 0 到 1000 依次把剩余计数追加到结果尾部自动满足「未出现在arr2中的元素按升序排列」的要求。复杂度分析从代码结构可以推断虽然存在两层嵌套的for循环但内层循环每执行一次都会消耗一个计数单位而所有计数单位的总和恰好等于len(A)。因此第一阶段为 O(len(A))第二阶段与第三阶段的内层总迭代次数均不超过 len(A)整体为 O(len(A) len(B) 1001)在本题约束下可视为线性时间空间上仅使用一个固定大小的[1001]int数组与结果切片空间复杂度 O(len(A))源码注释标记为 O(n^2) 属于保守估计实际内层循环迭代总量受数组长度严格约束。解法二哈希计数 剩余元素排序源码实现如下对应 1122. Relative Sort Array.go// 解法二 模拟时间复杂度 O(n^2) func relativeSortArray1(arr1 []int, arr2 []int) []int { leftover, m, res : []int{}, make(map[int]int), []int{} for _, v : range arr1 { m[v] } for _, s : range arr2 { count : m[s] for i : 0; i count; i { res append(res, s) } m[s] 0 } for v, count : range m { for i : 0; i count; i { leftover append(leftover, v) } } sort.Ints(leftover) res append(res, leftover...) return res }执行流程统计频次遍历arr1用map[int]int记录每个元素出现的次数按arr2顺序输出遍历arr2取出m[s]作为输出次数将s重复追加到结果中随后将m[s]置 0避免后续被再次统计收集剩余元素遍历 map将计数不为 0 的元素展开到leftover切片中排序并拼接调用标准库sort.Ints对leftover升序排序最后拼接到结果尾部。相比解法一该解法不依赖元素值域的大小对取值范围更大或元素为其他可排序类型的输入同样适用通用性更强。其时间复杂度由最后的sort.Ints主导为 O(k log k)k 为未出现在arr2中的元素个数k ≤ len(A)空间上需要额外的 map 与leftover切片空间复杂度 O(len(A))源码注释同样标记为 O(n^2) 保守估计。测试验证表驱动用例仓库为本题编写了标准的表驱动测试位于 1122. Relative Sort Array_test.gotype question1122 struct { para1122 ans1122 } // para 是参数 // one 代表第一个参数 type para1122 struct { arr1 []int arr2 []int } // ans 是答案 // one 代表第一个答案 type ans1122 struct { one []int } func Test_Problem1122(t *testing.T) { qs : []question1122{ { para1122{[]int{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}, []int{2, 1, 4, 3, 9, 6}}, ans1122{[]int{2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19}}, }, } for _, q : range qs { _, p : q.ans1122, q.para1122 fmt.Printf(【input】:%v 【output】:%v\n, p, relativeSortArray(p.arr1, p.arr2)) relativeSortArray1(p.arr1, p.arr2) } }测试采用了 LeetCode-Go 仓库统一的「para参数 ans期望答案」表驱动结构question1122聚合输入输出para1122保存arr1/arr2两个输入数组ans1122保存期望输出。用例覆盖了题面给出的标准示例同时调用relativeSortArray与relativeSortArray1两个实现进行验证。读者可在仓库根目录执行go test ./leetcode/1122.Relative-Sort-Array/ -v复现该用例仓库基于 Go 1.19见 go.mod。两种解法对比维度解法一定长桶计数解法二哈希计数 排序核心数据结构[1001]int定长数组map[int]int输出顺序依据桶下标天然有序最后依赖sort.Ints时间复杂度实际O(len(A) len(B) 1001)O(len(A) k log k)空间复杂度O(1001 len(A))O(len(A))适用前提元素值域有限且为整数本题 0–1000值域不受限通用性强依赖标准库无需额外导入需要sort选择建议当元素值域紧凑、已知且有限时本题即典型场景解法一的定长桶可以同时完成「按序输出」与「剩余升序」两项任务代码更短、常数更小当元素值域未知或范围过大时解法二的 map 排序方案更通用、扩展性更好。小结Relative Sort Array 是一道典型的「计数 顺序重排」应用题核心技巧在于先用计数结构数组桶或 map收集频次再以arr2的顺序作为主排序依据输出最后对剩余元素单独升序处理。LeetCode-Go 仓库在 题解文档 与 源码文件 中完整收录了这两种解法及对应测试用例读者可结合上述代码逐行推演进而举一反三将「外部顺序 升序兜底」的模式迁移到类似的排序改造类题目中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考