孤独像素 I
难度:
标签:
题目描述
代码结果
运行时间: 44 ms, 内存: 21.6 MB
/*
* 思路:
* 1. 使用流操作来计算每行和每列'B'的出现次数
* 2. 再次使用流操作来检查每个'B'是否是孤独像素
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class LonelyPixelIStream {
public int findLonelyPixel(char[][] picture) {
int m = picture.length;
int n = picture[0].length;
int[] rowCount = new int[m];
int[] colCount = new int[n];
// 记录每行和每列'B'的出现次数
IntStream.range(0, m).forEach(i ->
IntStream.range(0, n).forEach(j -> {
if (picture[i][j] == 'B') {
rowCount[i]++;
colCount[j]++;
}
})
);
// 计算孤独像素的数量
return (int) IntStream.range(0, m).flatMap(i ->
IntStream.range(0, n).filter(j ->
picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1
)
).count();
}
}
解释
方法:
这个题解的思路是先遍历整个二维数组,统计每一行和每一列中 'B' 的个数,记录在 cntRow 和 cntCol 两个数组中。然后再次遍历二维数组,对于每个 'B',如果它所在的行和列的 'B' 的个数都为 1,说明这个 'B' 是孤独像素,结果加 1。最后返回孤独像素的总数。
时间复杂度:
O(mn)
空间复杂度:
O(m+n)
代码细节讲解
🦆
在算法中,为什么需要两次遍历整个二维数组而不能通过一次遍历完成任务?
▷🦆
如果输入的二维数组中没有任何'B',算法的性能如何?是否有必要增加前置检查以提高效率?
▷🦆
代码中假设了输入至少有一个元素(即m和n都大于0),如果输入的数组为空或者非法,该如何处理以增强代码的鲁棒性?
▷