LeetCode 1380. Lucky number in matrix

1380. The lucky number in the matrix

To give you one m * n Matrix , The number in the matrix Each are not identical . Please press arbitrarily Return all the lucky numbers in the matrix in order .

Lucky number refers to the elements in the matrix that meet the following two conditions at the same time ：

• The smallest of all elements in the same row
• The largest of all elements in the same column

Example 1：

 Input ：matrix = [[3,7,8],[9,11,13],[15,16,17]]
 Output ：[15]
 explain ：15  Is the only lucky number , Because it is the smallest value in its row , It is also the maximum value in the column .

Example 2：

 Input ：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
 Output ：[12]
 explain ：12  Is the only lucky number , Because it is the smallest value in its row , It is also the maximum value in the column .

Example 3：

 Input ：matrix = [[7,8],[1,2]]
 Output ：[7]

Tips ：

• m == mat.length
• n == mat[i].length
• 1 <= n, m <= 50
• 1 <= matrix[i][j] <= 10^5
• All elements in the matrix are different

Two 、 Method 1

simulation

class Solution {
    
    public List<Integer> luckyNumbers (int[][] matrix) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                boolean isMin = true;
                boolean isMax = true;
                for (int k = 0; k < n; k++) {
    
                    if (matrix[i][k] < matrix[i][j]) {
    
                        isMin = false;
                        break;
                    }
                }
                if (!isMin) {
    
                    continue;
                }
                for (int k = 0; k < m; k++) {
    
                    if (matrix[k][j] > matrix[i][j]) {
    
                        isMax = false;
                        break;
                    }
                }
                if (isMax) {
    
                    res.add(matrix[i][j]);
                }
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity :：O(mn×(m+n)), among m and n These are matrices matrix The number of rows and columns . ergodic matrix matrix need O(mn), lookup 行 Minimum required O(n), Finding the maximum value of a column requires O(m).

• Spatial complexity ：O(1). The return value does not calculate the space complexity .

3、 ... and 、 Method 2

Storage

class Solution {
    
    public List<Integer> luckyNumbers (int[][] matrix) {
    
        int m = matrix.length;
        int n = matrix[0].length;
        int[] minRow = new int[m];
        int[] maxCol = new int[n];
        Arrays.fill(minRow, Integer.MAX_VALUE);
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                minRow[i] = Math.min(minRow[i], matrix[i][j]);
                maxCol[j] = Math.max(maxCol[j], matrix[i][j]);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
    
            for (int j = 0; j < n; j++) {
    
                if (maxCol[j] == matrix[i][j] && minRow[i] == matrix[i][j]) {
    
                    res.add(matrix[i][j]);
                }
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(mn), among m and n These are matrices matrix The number of rows and columns . Preprocessing minRow and maxCol need O(mn), Finding lucky numbers requires O(mn).

• Spatial complexity ：O(m+n). preservation minRow and maxCol need O(m+n) Extra space , The return value is not included in the space complexity .