leetcode
leetcode 1251 ~ 1300
矩阵中的幸运数

矩阵中的幸运数

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.4 MB


/*
 * 思路:
 * 1. 使用流操作来遍历矩阵的每一行,找到每一行的最小值及其对应的列索引。
 * 2. 对于每个最小值,检查其所在列是否为该列的最大值。
 * 3. 如果是,则这个值是幸运数,将其加入结果列表。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class LuckyNumbersStream {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> luckyNumbers = new ArrayList<>();
        IntStream.range(0, matrix.length).forEach(i -> {
            int minRowValue = IntStream.range(0, matrix[i].length)
                .mapToObj(j -> matrix[i][j])
                .min(Integer::compareTo)
                .get();
            int minRowIndex = IntStream.range(0, matrix[i].length)
                .filter(j -> matrix[i][j] == minRowValue)
                .findFirst()
                .getAsInt();
            boolean isMaxInCol = IntStream.range(0, matrix.length)
                .allMatch(k -> matrix[k][minRowIndex] <= minRowValue);
            if (isMaxInCol) {
                luckyNumbers.add(minRowValue);
            }
        });
        return luckyNumbers;
    }
}

解释

方法:

这个题解的核心思路是首先分别计算矩阵中每一行的最小值和每一列的最大值。对于每一行,找到其中的最小元素,并存储在列表 row_min 中。对于每一列,找到其中的最大元素,并存储在列表 col_max 中。之后,遍历整个矩阵的每一个元素,检查该元素是否既是所在行的最小值也是所在列的最大值。如果是,那么这个元素就是一个幸运数,并将其添加到结果列表 ans 中。

时间复杂度:

O(mn)

空间复杂度:

O(m + n)

代码细节讲解

🦆
在算法中如何确保每一行的最小值和每一列的最大值的计算是准确的,有没有可能会因为遍历顺序的问题而导致错误?
在算法中,我们分别计算每一行的最小值和每一列的最大值。对于每一行的最小值,我们对该行的所有元素进行遍历,找到最小的一个;对于每一列的最大值,则遍历该列的所有元素,寻找最大的一个。由于这里的行和列遍历是独立的,且每次我们只关心行内或列内的元素,遍历顺序不会影响到最终的最小值和最大值的计算。因此,不存在遍历顺序导致计算错误的问题。
🦆
算法在处理极端情况,如矩阵只有一行或一列时,其行为是怎样的?是否有必要对这种单行或单列的情况特别处理?
当矩阵只有一行时,该行的最小值同时也是这行的所有元素,而每一列的最大值也将是该元素自身,相似的逻辑适用于只有一列的情况。在这种极端情况下,算法仍然适用,不需要特别处理。每一个元素都会被检查是否同时是其行的最小值和列的最大值,因此,算法能正确处理单行或单列的情况。
🦆
在算法中,如果矩阵的元素值有正负,会对找幸运数的逻辑产生何种影响?
元素的正负不会影响找幸运数的逻辑。幸运数的定义是基于元素是否是所在行的最小值和所在列的最大值,这个判断与元素的正负无关。无论元素是正数、负数还是零,算法都是通过比较确定是否满足幸运数的条件。因此,元素的正负不会对找幸运数的过程产生任何影响。
🦆
在实际实现中,如何处理矩阵中的重复元素,尤其是当题目说明中提到矩阵中的数字各不相同,但实际输入违反这一假设时?
在实际实现中,如果矩阵中出现了重复元素,算法仍然可以正常运行,因为它独立地检查每个元素是否满足既是其行的最小值也是列的最大值的条件。即使有重复元素,这种检查不会受到影响。如果题目假设矩阵中的元素各不相同,实际输入却有重复,只要保证算法逻辑正确执行,即可正确地识别出所有幸运数。重复元素可能会导致多个相同的幸运数结果,但这不会影响算法的正确性和运行。

相关问题