[LeetCode] 1380. Lucky Numbers in a Matrix

Given an m x n matrix of distinct numbers, return all lucky 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.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 105.
All elements in the matrix are distinct.

矩阵中的幸运数。

给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。

幸运数 是指矩阵中满足同时下列两个条件的元素：

• 在同一行的所有元素中最小
• 在同一列的所有元素中最大

思路

这是一道二维矩阵的基础题，正常遍历这个二维数组。然后我们需要用两个一维数组分别记录每一行的最大值和每一列的最大值。接着我们再次遍历每一行的最大值和每一列的最大值，如果某一行的最大值恰巧是某一列的最小值，则把这个值加入结果集。

复杂度

时间O(mn)
空间O(m + n)

代码

Java实现

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        // corner case
        if (matrix == null || matrix.length == 0) {
            return new ArrayList<>();
        }

        // normal case
        int m = matrix.length;
        int n = matrix[0].length;
        int[] rows = new int[m];
        Arrays.fill(rows, Integer.MAX_VALUE);
        int[] cols = new int[n];
        Arrays.fill(cols, Integer.MIN_VALUE);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int val = matrix[i][j];
                rows[i] = Math.min(rows[i], val);
                cols[j] = Math.max(cols[j], val);
            }
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int cur = matrix[i][j];
                if (rows[i] == cur && cols[j] == cur) {
                    res.add(cur);
                }
            }
        }
        return res;
    }
}