CTF of Z2BNS
0%

矩阵中的幸运数

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
输出：[15]
解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例2：

1
2
3
输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
输出：[12]
解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例3：

1
2
输入：matrix = [[7,8],[1,2]]
输出：[7]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5
  • 矩阵中的所有元素都是不同的
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

暴力解法：遍历每一行，求出当前行中的最小元素，然后判断这个元素是否是所在列中的最大值，如果是则是幸运数，否则不是幸运数。

c++代码：(执行用时68ms，击败5.15%，内存消耗11.5M，击败17.44%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        vector<int> result;
        int m=matrix.size();
        int n=matrix[0].size();
        //遍历每一行
        for(int i=0;i<m;++i){
            //求出每一行的最大值
            int row_min=INT_MAX;
            //每一行最小值的列索引
            int min_j=0;
            for(int j=0;j<n;++j){
                if(matrix[i][j]<row_min){
                    row_min=matrix[i][j];
                    min_j=j;
                }
            }
            //判断当前行最小值是否是所在列最大的，即是否是幸运数
            int col_max=0;
            for(int k=0;k<m;++k){
                if(row_min<matrix[k][min_j]){
                    //不是幸运数
                    break;
                }else if(k==m-1){
                    //在当前列中最大，是幸运数
                    result.push_back(row_min);
                }
            }  
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一： 模拟

预处理出两个数组 rMin 和 cMax，其中 rMin[i] 表示第 $i$ 行中最小的元素，cMax[j] 表示第 $j$ 列中最大的元素。接着遍历矩阵 matrix，判断每个 matrix[i][j] 是否是这一行最小的并且是这一列最大的，具体方法是直接与 rMin[i] 和 cMax[j] 比较，如果都相等，就加入到答案的序列中。

思考：rMin 和 cMax 是否可以存放「行最小值」和「列最大值」的索引？ 答案是可以。但是如果原题中没有说明「矩阵中的数字 各不相同」就不能这么干，因为假设第 rr 行的「行最小值」出现两次，索引为 $c_1$ 和 $c_2$c ，却只保存了一个索引 $c_1$，$c_2$位置的这个数满足它是「列最大值」，这个时候就会判断出错。

c++代码：(执行用时60ms，击败5.15%，内存消耗11.6M，击败7.41%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int r = matrix.size(), c = matrix[0].size();
        vector<int> rMin(r, INT_MAX);
        vector<int> cMax(c, 0);
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                rMin[i] = min(rMin[i], matrix[i][j]);
                cMax[j] = max(cMax[j], matrix[i][j]);
            }
        }

        vector<int> ans;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if (matrix[i][j] == rMin[i] && matrix[i][j] == cMax[j]) {
                    ans.push_back(matrix[i][j]);
                }
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：预处理的时间代价是 $O(mn)$，统计答案的时间代价也是 $O(mn)$，故渐进时间复杂度为 $O(mn)$。

  • 空间复杂度：这里用到了两个辅助数组 rMin​ 和 cMax​，长度分别为 $m$ 和 $n$，故渐进空间复杂度为 $O(m + n)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

本来我觉得暴力模拟解法太low了，想看看题解有没有什么更好的方法，结果官方题解也是暴力模拟🤣，不过官方题解和我的还是有一些不一样，他是先求出每行的最小值和每列的最大值，我是求出每行的最小值后再去判断是否是该列的最大值，他是并列关系，我是递进关系，不过效率也都差不多😗。

------------- THE END! THANKS! -------------