LeetCode-Go 题解1337. The K Weakest Rows in a Matrix —— 利用1 恒在 0 前性质的按列扫描法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode-Go 仓库中 1337.The-K-Weakest-Rows-in-a-Matrix 题解目录 的完整文档与源码讲解矩阵中最弱的 K 行这一经典二维矩阵问题的两种解法最直观的计数 排序思路以及利用题目隐含有序性质、仓库实际采用的按列扫描高效解法。读完本文你将掌握如何从题目条件中提取有序性、把找最弱行转化为按列扫描 全 1 行补位的 O(m·n) 级实现并能独立阅读与运行该目录下的源码和测试。题目解读谁才是最弱的一行题目给出一个m * n的矩阵mat矩阵元素只有两类1代表军人soldiers0代表平民civilians。需要返回矩阵中战斗力最弱的前 k 行的索引且按从最弱到最强排序。强弱比较规则源自原文档第i行的军人数量少于第j行则第i行更弱若两行军人数量相同则行号更小的行更弱军人总是站在一行的靠前位置即每一行总是先出现若干个1之后才是0。也就是说本题的弱是双重维度下的有序比较先比军人个数少者弱再比行号小者弱。题目大意与原文一致请你返回矩阵中战斗力最弱的k行的索引按从最弱到最强排序。输入输出示例与数据约束示例 1原文档 Example 1输入mat [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]] k 3 输出[2,0,3] 各行军人数量row 0 - 2row 1 - 4row 2 - 1row 3 - 2row 4 - 5 按从最弱到最强排序为 [2,0,3,1,4]注意这里体现的比较细节row 0 与 row 3 军人数量都为 2因行号 0 3所以 row 0 排在 row 3 之前。示例 2原文档 Example 2输入mat [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]] k 2 输出[0,2] 各行军人数量row 0 - 1row 1 - 4row 2 - 1row 3 - 1 按从最弱到最强排序为 [0,2,3,1]约束条件原文档 Constraints约束取值矩阵行数m mat.length矩阵列数n mat[i].length规模2 n, m 100k 的范围1 k m元素取值mat[i][j]只能是0或1规模很小最大 100×100因此最直观的暴力计数方案在复杂度上也完全可行但本题真正的价值在于第二条解题思路利用了行内元素的有序性。核心性质军人总是排在一行的靠前位置原文档特别强调了一个看似多余的条件军人 总是 排在一行中的靠前位置也就是说 1 总是出现在 0 之前。这个条件意味着每一行都可以写成如下形式1 1 ... 1 0 0 ... 0 ← k 个 1 → ← 剩余 0 →即每一行的形态是1^k 0^(n-k)。由此可以推出两个有用的结论某行的军人数量等价于该行第一个出现0的列号若整行全为1则军人数量为n若按列优先先遍历第 0 列、再第 1 列……顺序扫描矩阵那么越早遇到第一个0的行军人数量越少——而按列扫描天然按行号从小到大访问恰好同时满足了军人数量少的排前面、数量相同时行号小的排前面这两个比较规则。解法二正是围绕这一性质设计的。解法一统计军人数量 排序最直观的思路原文档首先给出了人人都能想到的思路先统计每一行1的个数再按1 的个数升序、个数相同时按行号升序排序最后取前 k 个索引。以下是按该思路写出的示意实现仅供理解思路非仓库原码仓库最终采用的是解法二package leetcode import sort func kWeakestRowsCounting(mat [][]int, k int) []int { type rowPower struct { cnt int // 该行军人1的数量 idx int // 原始行号 } rows : make([]rowPower, 0, len(mat)) for i : 0; i len(mat); i { cnt : 0 for j : 0; j len(mat[i]); j { if mat[i][j] 1 { cnt } } rows append(rows, rowPower{cnt: cnt, idx: i}) } // 军人数量升序数量相同时行号升序 sort.Slice(rows, func(a, b int) bool { if rows[a].cnt ! rows[b].cnt { return rows[a].cnt rows[b].cnt } return rows[a].idx rows[b].idx }) res : make([]int, k) for i : 0; i k; i { res[i] rows[i].idx } return res }复杂度分析统计每行军人数量需要遍历整个矩阵为 O(m·n)排序为 O(m·log m)总时间复杂度 O(m·n m·log m)额外空间 O(m)。可以继续优化的点由于每行都是1^k 0^(n-k)的形态求军人数量时其实不必线性扫描整行可以在每行内做一次二分查找第一个0的位置把单行计数降到 O(log n)总复杂度变为 O(m·log n m·log m)。不过题目规模很小这种优化并非必须。这种解法虽然正确但它完全没有利用1 恒在 0 前这一条件原文档也明确指出解法二才是最优雅、最高效的解法。解法二按列扫描仓库采用的高效解法思路推导由于每一行都是1^k 0^(n-k)形态最先出现0的行一定军人最少。于是可以逐列扫描对第j列从上到下检查每一行i若mat[i][j] 0且这一行在更左侧第j-1列还是1或者j 0说明行i的第一个0恰好出现在第j列此时就把行号i追加进结果。因为外层按列j从小到大、内层按行i从小到大遍历所以军人数量少的行第一个0更靠左先被追加军人数量相同的行行号小的先被追加。这两条恰好完整对应题目定义的强弱比较规则连排序都不需要。最后再单独把整行全为 1的行按行号从小到大补到结果末尾即可。仓库源码仓库在 1337. The K Weakest Rows in a Matrix.go 中的实现与原文档给出的代码完全一致package leetcode func kWeakestRows(mat [][]int, k int) []int { res : []int{} for j : 0; j len(mat[0]); j { for i : 0; i len(mat); i { if mat[i][j] 0 ((j 0) || (mat[i][j-1] ! 0)) { res append(res, i) } } } for i : 0; i len(mat); i { if mat[i][len(mat[0])-1] 1 { res append(res, i) } } return res[:k] }逐行拆解第一个双重循环外层遍历列j0到n-1内层遍历行i0到m-1。判断条件mat[i][j] 0 ((j 0) || (mat[i][j-1] ! 0))的含义是当前元素是0且它的左侧元素是1或它本身就是第 0 列。这保证了每一行只在其第一个 0所在的列被追加一次不会重复入队。第二个循环遍历所有行若最后一列len(mat[0])-1仍为1说明该行全为1即军人数量达到最大值n应当排在所有出现0的行之后因此按行号递增依次追加。return res[:k]由约束1 k m保证切片不会越界直接截取前 k 个即为答案。以示例 1 验证第 0 列只有 row 2 是0追加2第 1 列 row 0、row 3 是第一个0追加0、3最终全 1 的 row 4 被补在末尾。得到res [2,0,3,4]取前 3 个即[2,0,3]与预期输出一致。复杂度分析外层循环最多扫描 m·n 个元素第二段循环扫描 m 行最坏时间复杂度 O(m·n)由于不需要额外的排序结构除了结果切片本身几乎无额外空间开销。相比解法一省去了排序且常系数更小从源码结构看是本题最优的实现方式。两种解法对比解法时间复杂度空间复杂度是否利用1 恒在 0 前特点解法一计数 排序O(m·n m·log m)O(m)否思路直观通用性强需要自定义排序规则解法二按列扫描最坏 O(m·n)O(1) 额外不含结果是代码更短无需排序利用有序性天然满足比较规则两种解法都满足题目的全部约束解法二在实现简洁度与常数性能上更优也是仓库 README 中明确推荐的最优雅最高效的解法。仓库源码与测试验证源码与测试文件结构该题在仓库中与其他题目保持完全一致的目录组织方式1337.The-K-Weakest-Rows-in-a-Matrix 目录 下包含三个文件README.md题目原文、大意、解题思路与代码The K Weakest Rows in a Matrix.go核心实现即上文解法二The K Weakest Rows in a Matrix_test.go单元测试。测试用例与运行方式测试文件 1337. The K Weakest Rows in a Matrix_test.go 定义了Test_Problem1337其中两个用例与原文档的 Example 1、Example 2 完全对应mat [[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]、k 3期望输出[2,0,3]mat [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]、k 2期望输出[0,2]。测试框架使用 Go 标准库testing并在用例中通过fmt.Printf打印输入与输出结果便于肉眼比对。在仓库根目录Go 版本为 1.19见 go.mod下可以单独运行该题测试go test ./leetcode/1337.The-K-Weakest-Rows-in-a-Matrix/ -run Test_Problem1337 -v也可以按仓库提供的 gotest.sh 方式对所有题解做整体覆盖率测试bash gotest.shgotest.sh 内部执行的是go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...生成仓库根目录下的 coverage.txt 覆盖率文件这体现了仓库每题必带测试、用覆盖率约束代码质量的组织约定。测试通过即证明解法二对两个官方示例均输出正确结果。边界情况与易错点全 1 行必须最后补位若遗漏第二个循环整行为1的行将永远不会被追加因为扫描循环只处理出现0的行导致结果缺少最强的行。这是本题最容易出错的地方。防止同一行重复入队扫描循环中(j 0) || (mat[i][j-1] ! 0)这个条件至关重要。去掉它一行内后续的每个0都会把该行再次追加破坏结果的长度与顺序。切片越界res[:k]依赖1 k m的约束保证安全若去掉该约束则需要先对res长度做防御性判断。比较规则的双重性按列扫描天然解决军人数量相同按行号排序的平局问题这是该解法优于只统计数量再直接排序不写稳定排序或自定义规则的根因。小结1337. The K Weakest Rows in a Matrix 是一道典型的条件即线索题目题目给出的军人总是排在一行靠前位置并非冗余信息而是将矩阵每一行约束成1^k 0^(n-k)的有序结构从而允许用按列扫描的方式在无需排序的情况下同时满足军人数量升序与行号升序两个比较维度。LeetCode-Go 仓库以解法二作为该题的标准答案并配套了与官方示例一一对应的单元测试。读者可以在此基础上进一步把二分查找每行第一个 0与按列扫描两种思路结合体会从题目条件中挖掘数据结构特性的通用方法论。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考