矩阵中的幸运数
难度:
标签:
题目描述
代码结果
运行时间: 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)
代码细节讲解
🦆
在算法中如何确保每一行的最小值和每一列的最大值的计算是准确的,有没有可能会因为遍历顺序的问题而导致错误?
▷🦆
算法在处理极端情况,如矩阵只有一行或一列时,其行为是怎样的?是否有必要对这种单行或单列的情况特别处理?
▷🦆
在算法中,如果矩阵的元素值有正负,会对找幸运数的逻辑产生何种影响?
▷🦆
在实际实现中,如何处理矩阵中的重复元素,尤其是当题目说明中提到矩阵中的数字各不相同,但实际输入违反这一假设时?
▷