LeetCode 1380. Lucky Numbers in a Matrix 幸运数查找：LeetCode-Go 单次遍历解法详解

LeetCode 1380. Lucky Numbers in a Matrix 幸运数查找LeetCode-Go 单次遍历解法详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode 第 1380 题「矩阵中的幸运数」为对象基于 LeetCode-Go 仓库的官方实现与配套单元测试完整讲解幸运数的判定规则、单次遍历的优化思路、逐行代码剖析与正确性论证。读完本文你将掌握如何在 O(m×n) 时间内仅用 O(n) 额外空间找出矩阵中的所有幸运数并能复现仓库的测试与覆盖率验证流程。题目定义与判定规则原题英文定义如下Given am * nmatrix ofdistinctnumbers, return all lucky numbers in the matrix inanyorder. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.题目大意原文中文版给你一个 m * n 的矩阵矩阵中的数字各不相同。请你按任意顺序返回矩阵中的所有幸运数。幸运数是指矩阵中满足同时下列两个条件的元素在同一行的所有元素中最小行内最小在同一列的所有元素中最大列内最大判定规则需要抓住两个要点双重身份一个元素必须同时具备「本行最小值」和「本列最大值」两个身份才算幸运数只满足其一不成立互异前提原题保证矩阵内所有元素互不相同因此「最小/最大」的判定不会出现并列歧义返回顺序任意any order即结果数组的排列顺序不影响判题正确性。输入输出示例与约束官方示例Example 1Input: matrix [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column15 位于第 2 行该行最小同时是第 0 列的最大值3、9、15 中最大因此是唯一幸运数。Example 2Input: matrix [[1,10,4,2],[9,3,8,7],[15,16,17,12]] Output: [12] Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.12 是第 2 行的最小值也是第 3 列2、7、12的最大值。Example 3Input: matrix [[7,8],[1,2]] Output: [7]7 是第 0 行的最小值也是第 0 列7、1的最大值。约束条件m mat.lengthn mat[i].length1 n, m 501 matrix[i][j] 10^5矩阵中所有元素互不相同约束对算法设计有两个直接影响m、n 最大仅为 50O(m×n) 甚至更宽松的算法都能通过评测但仓库实现选择了理论最优的 O(m×n) 单次遍历元素值全部 ≥ 1这使0可以安全地充当「未记录/未初始化」的哨兵值是下文源码实现能成立的前提。解题思路方案一朴素两遍扫描可读性优先原文解题思路指出这是简单题按照题意遍历矩阵找到同时满足 2 个条件的数输出即可。最直观的做法分两步第一遍扫描分别统计每一行的最小值rowMin[i]与每一列的最大值colMax[j]第二遍扫描遍历每个格子(i, j)若matrix[i][j] rowMin[i]且matrix[i][j] colMax[j]则该元素同时满足「行内最小 列内最大」即为幸运数。时间复杂度 O(m×n)额外空间 O(mn)两个辅助数组。方案二仓库实现的单次遍历空间更省LeetCode-Go 的官方实现 只做一遍扫描就把两件事同时完成一边求当前行的最小值m及其所在列号k一边滚动更新每列迄今的最大值t[j]若当前行最小值m恰好等于其所在列的迄今最大值t[k]说明它暂时是「行内最小 列内最大」先写入候选数组r[k]全部行处理完后再做一次终验候选值v仍等于t[k]才确认它没有被后续行更大的列值「顶掉」。相比朴素方案额外空间从 O(mn) 降为 O(n)只与列数相关并且在整个扫描过程中完成了大部分候选筛选无需二次遍历矩阵。源码逐行剖析完整实现如下与 题目源码 完全一致func luckyNumbers(matrix [][]int) []int { t, r, res : make([]int, len(matrix[0])), make([]int, len(matrix[0])), []int{} for _, val : range matrix { m, k : val[0], 0 for j : 0; j len(matrix[0]); j { if val[j] m { m val[j] k j } if t[j] val[j] { t[j] val[j] } } if t[k] m { r[k] m } } for k, v : range r { if v 0 v t[k] { res append(res, v) } } return res }第 1 步三个数组的初始化t, r, res : make([]int, len(matrix[0])), make([]int, len(matrix[0])), []int{}t记录每一列迄今为止的最大值长度等于列数n初值全部为 0r记录候选幸运数以下标为列号 k长度同样为n初值 0 兼任「未记录」哨兵res最终结果切片。因为所有元素值 ≥ 1初值 0 不会与真实数据混淆这是整个哨兵技巧成立的基础。第 2 步行遍历 列最大值滚动更新for _, val : range matrix { m, k : val[0], 0 for j : 0; j len(matrix[0]); j { if val[j] m { m val[j] k j } if t[j] val[j] { t[j] val[j] } } ... }内层循环同时干了两件事查找当前行最小值m及其列号k对应第 8-10 行滚动更新第j列的迄今最大值t[j]对应第 12-14 行。由于t初值为 0 且矩阵元素 ≥ 1第一行扫描时t[j] val[j]恒成立列最大值得以正确初始化。整个矩阵只需扫描一次即可同时获得所有行的最小值信息和所有列的累计最大值信息。第 3 步候选记录if t[k] m { r[k] m }内层循环结束时t[k]已经是「包含本行在内的第 k 列最大值」。此时若t[k] m说明m既是本行最小值又是迄今本列最大值先将其按列号写入候选数组r[k]。注意这里只是暂记候选因为后续行可能把第 k 列的最大值刷新得更大。第 4 步终验输出for k, v : range r { if v 0 v t[k] { res append(res, v) } } return resv 0表示该位置确实记录过候选0 是哨兵v t[k]验证候选在后续行中没有被超越即它仍是最终列最大值双重检查都通过的值才是货真价实的幸运数。为什么终验必不可少用一个反例说明。设矩阵为[[5,1],[6,7]]元素互异满足原题约束第 0 行最小值是 1第 1 列t [5, 1]t[1] 1于是r[1] 1第 1 行最小值是 6第 0 列同时第 1 列最大值被刷新为max(1, 7) 7t [6, 7]r[0] 6终验r[1] 1但t[1] 71 ! 7候选 1 被正确剔除r[0] 6且t[0] 6输出[6]。验证结果6 是第 1 行最小值6 7也是第 0 列最大值max(5, 6) 6确实是幸运数而 1 只是行内最小并非列内最大被终验拦截。若省略终验步骤1 就会被错误输出。正确性分析一个值得记录的数学性质互异矩阵中幸运数至多一个原题保证元素互异在此前提下可以严格证明幸运数至多只有一个。反证如下假设存在两个不同的幸运数 a 与 ba 位于 (r1, c1)b 位于 (r2, c2)。由于 a、b 分别是各自行的最小值、各自列的最大值必然有 r1 ≠ r2 且 c1 ≠ c2否则同一行出现两个最小值、或同一列出现两个最大值与互异矛盾。不妨设 a ba 是 r1 行最小值 ⇒a matrix[r1][c2]b 是 c2 列最大值 ⇒b matrix[r1][c2]于是a matrix[r1][c2] bb 是 r2 行最小值 ⇒b matrix[r2][c1]a 是 c1 列最大值 ⇒a matrix[r2][c1]于是matrix[r2][c1] a b与b matrix[r2][c1]直接矛盾。因此结论成立。推论返回值至多包含一个元素这也解释了三个官方示例的输出均为单元素数组面试中可以先「找候选、判存在」再决定是否返回不必担心结果数组膨胀。实现与性质的对应关系仓库实现并不显式依赖互异性质即使矩阵存在重复元素如测试用例 3候选记录 终验的逻辑依然能给出正确结果鲁棒性比「两遍扫描严格判等」更宽松一些。复杂度分析时间复杂度O(m×n)。两层循环恰好把矩阵每个元素访问一次没有任何重复扫描空间复杂度O(n)。t与r各为长度 n 的数组在互异前提下结果res至多容纳 1 个元素与朴素两遍扫描对比时间同为 O(m×n)空间上当列数 n 远小于行数 m 时O(n) 相比 O(mn) 优势明显。边界情况1×1 矩阵唯一元素既是行内最小又是列内最大天然是幸运数单行矩阵1×n每列只有一个元素恒为该列最大值因此幸运数唯一即整行的最小值单列矩阵m×1每行只有一个元素恒为该行最小值因此幸运数唯一即整列的最大值最值出现在边角判定只依赖行、列内的相对大小与元素位置无关逻辑不受影响元素重复放宽约束如测试用例[[1,2,3,4,5],[1,2,3,4,5]]实现仍能输出[1]1 同时是两行的最小值与第 0 列的最大值。测试验证与覆盖率仓库为本题配备了独立的单元测试 1380. Lucky Numbers in a Matrix_test.go采用结构体驱动的表格测试风格question1380组合para1380与ans1380共 4 个用例输入矩阵期望输出用例来源[[3,7,8],[9,11,13],[15,16,17]][15]README 示例 1[[1,10,4,2],[9,3,8,7],[15,16,17,12]][12]README 示例 2[[1,2,3,4,5],[1,2,3,4,5]][1]附加用例放宽互异约束[[7,8],[1,2]][7]README 示例 3其中用例 3 值得注意它并不满足原题「元素互不相同」的约束属于对实现的额外压力测试验证了算法不依赖互异性质。在仓库根目录执行以下命令即可运行本题测试go test -v ./leetcode/1380.Lucky-Numbers-in-a-Matrix/覆盖率方面仓库根目录的 coverage.txt 中记录了本题函数的全部执行块覆盖计数均为正说明测试完整执行了幸运数函数的每一行逻辑。全仓库覆盖率由 gotest.sh 统一生成核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...模块信息见 go.modmodule github.com/halfrost/LeetCode-GoGo 版本 1.19。此外仓库主 README 声明全部题解遵循 Google Golang Style Guide 代码风格本题实现同样是这一风格约束下的产物。小结幸运数的本质一个元素 行内最小 ∩ 列内最大两个条件缺一不可核心解法LeetCode-Go 用单次遍历 两个长度为 n 的数组完成判定时间复杂度 O(m×n)、额外空间 O(n)终验步骤候选记录后必须复核v t[k]防止候选被后续行更大的列值「顶掉」互异性质互异矩阵中幸运数至多一个可用于快速判空与面试推导加分。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考