### 题目描述 给你一个$$m \times 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] ``` **提示** - m == mat.length - n == mat[i].length - 1 <= n, m <= 50 - 1 <= matrix[i][j] <= 10^5 - 矩阵中的所有元素都是不同的 ### 题目解答 #### 题目思路 遍历每一行，寻找每行最小值。 再最小值对应列，如果没有值更大那么加入幸运数序列。 **复杂度** 数组大小为m行，n列。 时间复杂度：遍历每一行寻找最小，然后再找对应列，因此复杂度$$O(mn)$$ 空间复杂度：记录其中几个最大最小值，复杂度$$O(1)$$ #### 代码实现 ```java class Solution { public List<Integer> luckyNumbers (int[][] matrix) { List<Integer> res = new ArrayList<>(); for(int i=0;i<matrix.length;i++){ int min = Integer.MAX_VALUE; int min_id = 0; for(int j=0;j<matrix[0].length;j++){ if(matrix[i][j] < min){ min = matrix[i][j]; min_id = j; } } int k; for(k=0;k<matrix.length;k++){ if(matrix[k][min_id] > min) break; } if(k==matrix.length) res.add(matrix[i][min_id]); } return res; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复