1380. 矩阵中的幸运数
1380. 矩阵中的幸运数
题目
Given an m x n matrix of distinct numbers, return alllucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: 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 column.
Example 2:
Input: 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.
Example 3:
Input: matrix = [[7,8],[1,2]]
Output: [7]
Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.
Constraints:
m == mat.lengthn == mat[i].length1 <= n, m <= 501 <= matrix[i][j] <= 10^5.- All elements in the matrix are distinct.
题目大意
给你一个 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] <= 10^5- 矩阵中的所有元素都是不同的
解题思路
幸运数是指一个元素，它既是所在行的最小值，又是所在列的最大值。
在解决这个问题时，我们首先可以观察到，矩阵中 最多只有一个幸运数，可以通过 反证法 来证明这一点。
矩阵中最多只有一个幸运数
1. 假设有两个幸运数 X 和 Y
c2 c1
| |
r1 ---+-------------- X ---
| |
| |
| |
r2 -- Y --------------+----
| |
假设矩阵中有两个幸运数 X 和 Y，它们分别位于不同的位置：
X位于第r1行第c1列。Y位于第r2行第c2列。
根据题目定义，X 和 Y 都是幸运数，意味着：
X是第r1行的最小值，并且是第c1列的最大值。Y是第r2行的最小值，并且是第c2列的最大值。
2. Y < X
c2 c1
| |
r1 ---+-------------- X ---
| |
| |
| |
r2 -- Y ------------- A ---
| |
假设 A 点位于第 r2 行第 c1 列，则可以得到：
X > A，因为X是第c1列的最大值。Y < A，因为Y是第r2行的最小值。
因此可以得到：Y < X
3. Y > X
c2 c1
| |
r1 -- B ------------- X ---
| |
| |
| |
r2 -- Y ------------- A ---
| |
假设 B 点位于第 r1 行第 c2 列，则可以得到：
X < B，因为X是第r1行的最小值。Y > B，因为Y是第c2列的最大值。
因此可以得到：Y > X
4. 得出矛盾
从上面的描述可以看出，如果 X 和 Y 都是幸运数，当它们位于不同的行和列时，那么可以推出 Y < X 和 Y > X，这两个结论相互冲突，即不可能同时存在两个幸运数。
通过反证法，我们得出结论：矩阵中至多只有一个幸运数。
找出幸运数
- 幸运数字是所在行的最小值，又是所在列的最大值。
- 首先，找到每行的最小元素，然后将这些最小值中的最大值确定为
rowMinMax。 - 同样，找到每列的最大值，然后将这些最大值中的最小值确定为
colMaxMin。 - 如果
rowMinMax等于colMaxMin，则该值就是幸运数字； - 否则，返回一个空数组。
复杂度分析
- 时间复杂度：
O(m * n)，其中m是行数，n是列数，遍历每一行和每一列各一次。 - 空间复杂度：
O(1)，只使用了常数空间来存储变量
代码
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var luckyNumbers = function (matrix) {
const m = matrix.length;
const n = matrix[0].length;
// 找到每行的最小值
let rowMinMax = -Infinity;
for (let i = 0; i < m; i++) {
let rowMin = Infinity;
for (let j = 0; j < n; j++) {
rowMin = Math.min(rowMin, matrix[i][j]);
}
rowMinMax = Math.max(rowMinMax, rowMin);
}
// 找到每列的最大值
let colMaxMin = Infinity;
for (let i = 0; i < n; i++) {
let colMax = -Infinity;
for (let j = 0; j < m; j++) {
colMax = Math.max(colMax, matrix[j][i]);
}
colMaxMin = Math.min(colMaxMin, colMax);
}
// 判断是否为幸运数
if (rowMinMax === colMaxMin) {
return [rowMinMax];
}
return [];
};