LeetCode 题解工作台
矩阵中的幸运数
给你一个 m x n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。 幸运数 是指矩阵中满足同时下列两个条件的元素： 在同一行的所有元素中最小 在同一列的所有元素中最大 示例 1： 输入： matrix = [[3,7,8],[9,11,13],[15,16,17]] …
2
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·matrix
答案摘要
我们可以使用两个数组 和 记录矩阵中每一行的最小值和每一列的最大值，然后遍历矩阵中的每一个元素，检查该元素是否为所在行的最小值且为所在列的最大值，如果是则该元素为幸运数，我们将其加入答案数组。 遍历结束后，我们返回答案数组即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个 m x n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
幸运数 是指矩阵中满足同时下列两个条件的元素：
- 在同一行的所有元素中最小
- 在同一列的所有元素中最大
示例 1：
输入：matrix = [[3,7,8],[9,11,13],[15,16,17]] 输出：[15] 解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
示例 2：
输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]] 输出：[12] 解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
示例 3：
输入：matrix = [[7,8],[1,2]] 输出：[7] 解释：7 是唯一的幸运数字，因为它是行中的最小值，列中的最大值。
提示：
m == mat.lengthn == mat[i].length1 <= n, m <= 501 <= matrix[i][j] <= 105- 矩阵中的所有元素都是不同的
解题思路
方法一：维护行最小值和列最大值
我们可以使用两个数组 和 记录矩阵中每一行的最小值和每一列的最大值，然后遍历矩阵中的每一个元素，检查该元素是否为所在行的最小值且为所在列的最大值，如果是则该元素为幸运数，我们将其加入答案数组。
遍历结束后，我们返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
rows = {min(row) for row in matrix}
cols = {max(col) for col in zip(*matrix)}
return list(rows & cols)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N * M) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
The candidate can efficiently identify the row minimums and column maximums.
- question_mark
They correctly validate the lucky number condition for each element.
- question_mark
They optimize the solution by ensuring minimal space usage.
常见陷阱
外企场景- error
Failing to identify the correct row minimums or column maximums, leading to incorrect results.
- error
Not properly validating that a row minimum is also the column maximum.
- error
Using excessive space by storing unnecessary intermediate data or using complex data structures.
进阶变体
外企场景- arrow_right_alt
What if the matrix has non-distinct values? How would the solution change?
- arrow_right_alt
Can the matrix contain negative numbers? If so, how does it affect the solution?
- arrow_right_alt
What if we have to find lucky numbers for submatrices instead of the entire matrix?