每日一题:LeetCode:1380.矩阵中的幸运数

浏览次数 : 次 2022-02-15

博文字数统计 : 792字 | 阅读所需时长 : 3分

× 文章目录

1. 2022-02-15：LeetCode：1380.矩阵中的幸运数
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：暴力模拟

每日一题：LeetCode：1380.矩阵中的幸运数
- 时间：2022-02-15
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：数组
- 算法：模拟

2022-02-15：LeetCode：1380.矩阵中的幸运数

1. 题目描述

题目：原题链接
- 给你一个 m * n 的矩阵，矩阵中的数字各不相同，请你按任意顺序返回矩阵中的所有幸运数。
- 幸运数是指矩阵中满足同时下列两个条件的元素：
  - 在同一行的所有元素中最小
  - 在同一列的所有元素中最大
- m == mat.length
- n == mat[i].length
- 1 <= n, m <= 50
- 1 <= matrix[i][j] <= 10^5
- 矩阵中的所有元素都是不同的
输入输出规范
- 输入：二维数组
- 输出：幸运数构成的List
输入输出示例
- 输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
- 输出：[15]

2. 方法一：暴力模拟

思路
- 根据幸运数的定义，需要同时满足是每行最小且每列最大的数
- 那么无法避免对整个二维数组的遍历，考虑暴力模拟
- 我们维护两个数组：rowMin表示每行最小值，colMax表示每列最大值，遍历一次二维数组，更新这两个最值
- 然后再次遍历二维数组，对于遍历到的元素[i, j]，判断其是否同时等于rowMin中该行最小值，以及colMax中该列的最大值，相等就是幸运数，放入结果集中

题解

public List<Integer> luckyNumbers (int[][] matrix) {
    if(matrix == null || matrix.length == 0) return null;
    int m = matrix.length, n = matrix[0].length;
    int[] rowMin = new int[m];
    int[] colMax = new int[n];
    Arrays.fill(rowMin, Integer.MAX_VALUE);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            rowMin[i] = Math.min(rowMin[i], matrix[i][j]);
            colMax[j] = Math.max(colMax[j], matrix[i][j]);
        }
    }
    List<Integer> list = new ArrayList<>();
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                list.add(matrix[i][j]);
            }
        }
    }
    return list;
}

复杂度分析：m 和 n 分别是矩阵的行数、列数
- 时间复杂度：$O(m*n)$
- 空间复杂度：$O(Max(m, n))$
优化：常量空间
- 实际上，我们无需使用额外的空间来记录每行、每列的最值
- 这是因为当我们遍历二维数组找到当前行的最小值时，可以直接再去判断该元素是否是其所在列的最大值
- 此时可以在遍历过程中判断是否是幸运数，并添加到结果集中

题解

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            int rowMin = matrix[i][0], minIdx = 0;
            // 找到行的最小值
            for (int j = 1; j < n; j++) {
                if (rowMin > matrix[i][j]) {
                    rowMin = matrix[i][j];
                    minIdx = j;
                }
            }
            int colMax = rowMin;
            for (int j = 0; j < m; j++) {
                colMax = Math.max(colMax, matrix[j][minIdx]);
            }
            if (rowMin == colMax) {
                list.add(colMax);
            }
        }
        return list;
    }
}

优化后复杂度分析：m 和 n 分别是矩阵的行数、列数
- 时间复杂度：$O(m*Max(n, m))$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-02-15 23:21:50
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:1380.矩阵中的幸运数
本文链接： https://chthollists.github.io/post/e376af87.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！