LeetCode-Go 题解1051. Height Checker 身高检查器——排序比对法求最小移动人数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1051. Height Checker 的题解文档为核心完整讲解该题的题意、约束、解题思路、Go 实现与测试验证。读完本文你将掌握「排序 逐位比对」这一处理数组有序性问题的基础范式并能在 O(n log n) 时间内精确计算让数组变为非递减序列所需移动的最小人数同时了解仓库源码与测试的组织方式。题目回顾LeetCode 原题描述如下Students are asked to stand in non-decreasing order of heights for an annual photo. Return the minimum number of students that must move in order for all students to be standing in non-decreasing order of height.即学校拍年度纪念照时要求学生按照非递减non-decreasing的高度顺序排列。给定当前高度数组heights请返回能让所有学生以非递减高度排列所需的最小必要移动人数。题目还特别补充了一个关键条件Notice that when a group of students is selected they can reorder in any possible way between themselves and the non selected students remain on their seats.也就是说被选中的一组学生之间可以任意重新排序而未被选中的学生必须保持原位不动。这个条件决定了计数方式详见后文解题思路。数据约束约束项取值范围heights.length1 n 100heights[i]1 heights[i] 100数据规模极小最长 100 个元素、值域仅 1~100这意味 O(n log n) 甚至 O(n²) 的算法都能轻松通过但仓库采用了最标准的排序解法。三个官方示例示例 1Input: heights [1,1,4,2,1,3] Output: 3官方逐步推导如下Current array : [1,1,4,2,1,3] Target array : [1,1,1,2,3,4]索引 20 起始当前位置是4目标位置是1该学生必须移动索引 4当前位置是1目标位置是3该学生必须移动索引 5当前位置是3目标位置是4该学生必须移动。合计 3 人。注意索引 3 处2 2无需移动。示例 2Input: heights [5,1,2,3,4] Output: 5除5外的四个元素各差一位加上5本身五个位置全部错位答案为 5。示例 3Input: heights [1,2,3,4,5] Output: 0数组已经是有序的无需任何移动。解题思路排序 逐位比对为什么排序后逐位比对即可题目的约束是被选中的一组学生可以任意方式重排未被选中的保持不动。要让最终排列成为非递减序列最终形态必然是原数组排序后的结果——因为重排不改变学生集合只是调整顺序而非递减排列是唯一的值相等时位置可互换但计数结果不变。因此最少移动人数就是当前数组与排序后数组在相同下标上值不相等的个数。每发现一个错位就意味着该位置的学生必须被选中并参与重排。算法步骤复制一份heights数组作为对照对副本调用sort.Ints原地升序排序得到目标数组遍历原数组逐位与排序后的数组比较heights[i] ! checker[i]则计数加一返回计数值。仓库文档中给出的中文解题思路也精确地概括了这一过程简单题最少次数意味着每次移动一步到位一步就移动到它所在的最终位置。那么用一个辅助排好序的数组一一比对计数即可。仓库 Go 实现逐行解读仓库的实际实现位于 1051. Height Checker.go完整代码如下package leetcode import sort func heightChecker(heights []int) int { result, checker : 0, []int{} checker append(checker, heights...) sort.Ints(checker) for i : 0; i len(heights); i { if heights[i] ! checker[i] { result } } return result }逐行要点checker : []int{}与append(checker, heights...)这是本实现的关键技巧。append结合展开语法heights...会分配一块新的底层数组并把heights的全部元素拷贝进去从而避免直接checker : heights共享底层数组——那样排序会同时破坏原数组导致后续比对全部失效。从源码结构看这里采用先声明空切片再 append的写法与make([]int, len(heights))copy等价均实现了深拷贝。sort.Ints(checker)Go 标准库对[]int的原地升序排序排序完成后checker即目标非递减数组。逐位比对循环以len(heights)为界遍历一旦发现heights[i] ! checker[i]说明下标i位置的学生必须移动result。返回值result即最小必要移动人数。该实现不修改输入切片、不使用额外状态函数签名与 LeetCode 平台要求一致可直接在 OJ 上运行。单元测试验证仓库为本题编写了完整的表驱动测试位于 1051. Height Checker_test.go共覆盖 4 组用例输入heights期望输出说明[1,1,4,2,1,3]3官方示例 1[5,1,2,3,4]5官方示例 2[1,2,3,4,5]0官方示例 3已有序[5,4,3,2,1]4仓库补充的倒序用例测试代码采用该仓库统一的结构化用例组织方式type question1051 struct { para1051 ans1051 } // para 是参数 // one 代表第一个参数 type para1051 struct { one []int } // ans 是答案 // one 代表第一个答案 type ans1051 struct { one int }其中para1051封装输入参数、ans1051封装期望答案二者组合成question1051用例切片在Test_Problem1051中遍历断言。最后补充的倒序用例[5,4,3,2,1]很有教学价值排序后目标为[1,2,3,4,5]逐位比对只有 4 处不等中间值3恰好落在正确位置说明倒序数组 ≠ 全员移动印证了逐位比对计数而非按整体乱序程度估值的正确性。运行测试在仓库根目录执行标准 Go 测试命令即可验证本题实现仓库通过 gotest.sh 统一产出覆盖率文件其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...go test -v ./leetcode/ -run Test_Problem1051复杂度分析维度复杂度说明时间复杂度O(n log n)瓶颈是sort.Ints对 n 个元素排序比对阶段仅一次线性扫描 O(n)空间复杂度O(n)checker切片完整复制了一份输入数组在本题约束n ≤ 100下排序耗时可忽略不计这也是仓库选择标准排序解法的原因——代码简洁、语义清晰、易于验证。扩展思考优化方向利用值域做计数排序题目约束1 heights[i] 100意味着值域固定且很小可以进一步优化到 O(n 100) 的时间复杂度先统计每个高度值的出现频次再按值域顺序重建目标序列之后同样逐位比对计数。这样排序阶段不再是比较排序而退化为一次计数。不过该思路在 n ≤ 100 的场景下优势并不明显且会牺牲代码的直观性因此仓库保留了标准排序实现读者可在面试追问能否更快时作为加分项提出。同类题联想排序后与目标态比对的思想在数组类简单题中非常常见例如同样收录在本仓库 Array 专题 与 Sorting 专题 下的若干题目都涉及目标排列与当前排列的比较。掌握本题的深拷贝 → 排序 → 逐位比对三步范式可以迁移到身高、座位、评分等一切重排到有序状态求差异量的场景。参考文件索引题目文档本指南主体Go 实现源码单元测试仓库排序专题索引仓库数组专题索引仓库总 README题号索引【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考