Easy

题目描述

给你一个 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.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5
  • 矩阵中的所有元素都是不同的

解题思路

这道题要求找到矩阵中的幸运数，即在其所在行中最小、在其所在列中最大的元素。

解法思路：

  1. 预处理法（推荐）：先遍历矩阵，找出每行的最小值和每列的最大值，然后再次遍历矩阵检查每个元素是否同时满足两个条件。

    • 时间复杂度：O(m×n)，需要两次遍历
    • 空间复杂度：O(m+n)，存储每行最小值和每列最大值

  2. 直接判断法：对于矩阵中的每个元素，直接检查它是否为所在行的最小值和所在列的最大值。

    • 时间复杂度：O(m×n×(m+n))，对每个元素都要遍历整行和整列
    • 空间复杂度：O(1)

  3. 数学优化法：由于矩阵中所有元素都不相同，实际上最多只能有一个幸运数。可以找到所有行最小值中的最大值，和所有列最大值中的最小值，如果相等就是幸运数。

这里采用预处理法，既保证了效率，又便于理解。先用两个数组分别记录每行的最小值和每列的最大值，然后遍历矩阵找到同时满足条件的元素。

代码实现

class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        
        // 找每行的最小值
        vector<int> rowMin(m, INT_MAX);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rowMin[i] = min(rowMin[i], matrix[i][j]);
            }
        }
        
        // 找每列的最大值
        vector<int> colMax(n, INT_MIN);
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                colMax[j] = max(colMax[j], matrix[i][j]);
            }
        }
        
        vector<int> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    result.push_back(matrix[i][j]);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        
        # 找每行的最小值
        row_min = [min(row) for row in matrix]
        
        # 找每列的最大值
        col_max = [max(matrix[i][j] for i in range(m)) for j in range(n)]
        
        result = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == row_min[i] and matrix[i][j] == col_max[j]:
                    result.append(matrix[i][j])
        
        return result

public class Solution {
    public IList<int> LuckyNumbers(int[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        
        // 找每行的最小值
        int[] rowMin = new int[m];
        for (int i = 0; i < m; i++) {
            rowMin[i] = matrix[i].Min();
        }
        
        // 找每列的最大值
        int[] colMax = new int[n];
        for (int j = 0; j < n; j++) {
            colMax[j] = int.MinValue;
            for (int i = 0; i < m; i++) {
                colMax[j] = Math.Max(colMax[j], matrix[i][j]);
            }
        }
        
        List<int> result = new List<int>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    result.Add(matrix[i][j]);
                }
            }
        }
        
        return result;
    }
}

var luckyNumbers = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];
    
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const current = matrix[i][j];
            
            // Check if it's minimum in its row
            let isMinInRow = true;
            for (let k = 0; k < n; k++) {
                if (matrix[i][k] < current) {
                    isMinInRow = false;
                    break;
                }
            }
            
            // Check if it's maximum in its column
            let isMaxInCol = true;
            for (let k = 0; k < m; k++) {
                if (matrix[k][j] > current) {
                    isMaxInCol = false;
                    break;
                }
            }
            
            if (isMinInRow && isMaxInCol) {
                result.push(current);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(m×n)
空间复杂度O(m+n)

其中 m 为矩阵的行数，n 为矩阵的列数。时间复杂度为 O(m×n) 是因为需要遍历矩阵两次，空间复杂度为 O(m+n) 是因为需要额外存储每行的最小值和每列的最大值。