1380. Lucky Numbers in a Matrix

Leetcode link

题目简介

本题是一道简单题，但是其中还是有比较有趣的点值得思考的

题目给了我们一个二维数组，要求我们找到数组中的 Lucky number（定义为当前行最小且当前列最大）

解题思路1——模拟

第一种解法非常简单粗暴，我们遍历数组两次，第一次找出每一行的最小值，并且将其值记录下来

第二次找出每一列的最大值，如果在记录的最小值中有这个数，把它放进数组 res 保存起来

最后返回数组 res

复杂度分析：

• 时间复杂度是 $O(n^2)$
• 空间复杂度是 $O(n)$

Javascript

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var luckyNumbers  = function(matrix) {
    const minIndex = [];
    const res = [];

    // find minimum number in each row
    for(let i=0;i<matrix.length;i++) {
        let minNum = Number.MAX_VALUE;
        for(const row of matrix[i]) {
            minNum = Math.min(row, minNum);
        }
          // 用一个数组记录每一行的最小值
        minIndex.push(minNum);
    }

    // find max number in each column
    for(let i=0;i<matrix[0].length;i++) {
        let maxNum = 0
        for(let j=0;j<matrix.length;j++) {
            maxNum = Math.max(maxNum, matrix[j][i]);
        }
          // 找出每一列的最大值后在 minIndex 中查找，如果有就是 Lucky number
        if(minIndex.includes(maxNum)) {
            res.push(maxNum);
        }
    }
    return res;
};

解题思路2——进一步分析

这道题最鸡贼的点在于，它要求我们返回一个数组，且题目跟我们说的是找到 lucky numbers

这两点疯狂暗示我们 lucky number 有多个，但是实际上是如此吗？

我们来简单分析一下：

首先我们假设有多个 lucky numbers，那么这些 lucky numbers 一定是在斜对角上，举个例子：

[[x, A],
[B, y]]

我们有一个包含有 4 个元素的二维数组，我们假设其中的 A 跟 B 都是 lucky number，根据题目定义得知：

• A <= x && A >= y
• B <= y && B >= x

我们把上述两个条件联立起来，可以得到下面的结论：

• B >= x >= A
• A >= y >= B

我们再把这两个式子简化一下可得：

• B >= A
• A >= B

至此，可以得到：A === B

由此可知，如果二维数组要存在多个 lucky numbers，多个 lucky numbers 必须相等

题目给出了另外一点要求：Given an m x n matrix of distinct numbers

由此可知，本题的答案是唯一的

废了这么大劲得到了这个结论，可以做什么呢？

我们可以借由这个结论去减少空间复杂度

具体思路：既然只有一个答案，我们可以在遍历找到当前行的最小值的当下，遍历一下最小值的列，如果这个行最小值同时是列最大值，直接返回就好，如果不是继续遍历，知道最后如果都没有找到这个值，返回空数组 []

Javascript

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var luckyNumbers  = function(matrix) {
    for(let i = 0;i < matrix.length;i++) {
        // 找到当前行的最小值
        const min = Math.min(...matrix[i]);
        // 找出当前行的最小值在哪一列
        const colIndex = matrix[i].indexOf(min);
        // 对比最小值所在列的所有数字，如果都比最小值小（就是最小值是当列最大值）
        // 这就是 Lucky number，直接返回
        if(matrix.every(row => row[colIndex] <= min)) {
            return [min];
        }
    }
    return [];
};