This is the 28th day of my participation in the First Challenge 2022

preface

  • Some love each other, some drive at night to watch the sea, someleetcodeYou can’t do the first one, so you can see,leetcodeThe problem has weight. Today we’re going to meet them

Title address

Lucky numbers in a matrix

Subject to introduce

I give you an m by n matrix with different numbers in it. Return all lucky numbers in the matrix in any order.

A lucky number is an element in a matrix that satisfies both the following conditions:

Smallest of all elements in the same row and largest of all elements in the same column

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] output: [15] explanation: 15 is the only lucky number because it is the minimum value in its row and the maximum value in its column.Copy the code

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 because it is the smallest value in its row and the largest value in its column.Copy the code

Example 3:

Matrix = [[7,8],[1,2]]Copy the code

 

Tip:

M == mat.length n == mat[I]. Length 1 <= n, m <= 50 1 <= matrix[I][j] <= 10^5 All elements in the matrix are differentCopy the code

simulation

Train of thought

Traverse matrix matrix and judge whether matrix[I][j] is the minimum value of its row and the maximum value of its column. If so, add the returned result.

solution

var luckyNumbers = function(matrix) { const m = matrix.length, n = matrix[0].length; const ret = []; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { let isMin = true, isMax = true; for (let k = 0; k < n; k++) { if (matrix[i][k] < matrix[i][j]) { isMin = false; break; } } if (! isMin) { continue; } for (let k = 0; k < m; k++) { if (matrix[k][j] > matrix[i][j]) { isMax = false; break; } } if (isMax) { ret.push(matrix[i][j]); } } } return ret; };Copy the code

pretreatment

Train of thought

  • Preprocess minRow for each row and maxCol for each column.
  • Where minRow[I] represents the minimum value of row I and maxCol[j] represents the maximum value of column J.
  • If matrix[I][j] satisfies both matrix[I][j]=minRow[I] and matrix[I][j]=maxCol[j], then matrix[I][j] is a lucky number in the matrix

solution

var luckyNumbers  = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const minRow = new Array(m).fill(Number.MAX_SAFE_INTEGER);
    const maxCol = new Array(n).fill(0);
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            minRow[i] = Math.min(minRow[i], matrix[i][j]);
            maxCol[j] = Math.max(maxCol[j], matrix[i][j]);
        }
    }
    const ret = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === minRow[i] && matrix[i][j] === maxCol[j]) {
                ret.push(matrix[i][j]);
            }
        }
    }
    return ret;
};
Copy the code

Write in the last

  • I hope you find it rewarding