难度: Medium
Submission
运行时间: 44 ms
内存: 21.6 MB
class Solution:
def findLonelyPixel(self, picture: List[List[str]]) -> int:
m, n = len(picture), len(picture[0])
cntRow, cntCol = [0]*m, [0]*n
for i in range(m):
for j in range(n):
if picture[i][j] == 'B':
cntRow[i] += 1
cntCol[j] += 1
#print(cntRow, cntCol)
res = 0
for i in range(m):
for j in range(n):
if picture[i][j] == 'B' and cntRow[i] == 1 and cntCol[j] == 1:
res += 1
return res
Explain
这个题解的思路是先遍历整个二维数组，统计每一行和每一列中 'B' 的个数，记录在 cntRow 和 cntCol 两个数组中。然后再次遍历二维数组，对于每个 'B'，如果它所在的行和列的 'B' 的个数都为 1，说明这个 'B' 是孤独像素，结果加 1。最后返回孤独像素的总数。
时间复杂度: O(mn)
空间复杂度: O(m+n)
class Solution:
def findLonelyPixel(self, picture: List[List[str]]) -> int:
m, n = len(picture), len(picture[0])
cntRow, cntCol = [0]*m, [0]*n
# 遍历二维数组，统计每行每列的 'B' 的个数
for i in range(m):
for j in range(n):
if picture[i][j] == 'B':
cntRow[i] += 1
cntCol[j] += 1
res = 0
# 再次遍历二维数组，对每个 'B' 判断它是否是孤独像素
for i in range(m):
for j in range(n):
if picture[i][j] == 'B' and cntRow[i] == 1 and cntCol[j] == 1:
res += 1
return res
Explore
在第一次遍历中，我们需要统计每行和每列中'B'的个数。这是必要的步骤，因为仅有这样的统计后，我们才能确定哪些'B'是孤独的。如果尝试在一次遍历中完成这个任务，我们在处理某个'B'时可能还没有完整的信息来判断其所在行或列的'B'是否唯一。例如，如果在遍历过程中第一次遇到某行或列的'B'，我们无法立即知道该行或列后面是否还会有其他'B'。因此，两次遍历是必要的：第一次遍历用于收集信息，第二次遍历用于使用这些信息来确定孤独像素。
如果输入的二维数组中没有任何'B'，算法的第一次遍历将检测到每行和每列的'B'计数都为0。第二次遍历仍然会执行，但不会找到任何孤独的'B'。这种情况下，算法的时间复杂度仍然是O(m*n)，其中m和n分别是数组的行数和列数。虽然增加一个前置检查可以在一些极端情况下提高效率（例如，当整个数组均为空时直接返回0），但增加这样的检查可能会对算法的常规性能造成轻微的影响，因为它为每种情况都增加了额外的检查。因此，是否增加这样的前置检查取决于输入数据的预期特性以及对算法性能的具体要求。
为了增强代码的鲁棒性，我们应该在函数的开始添加检查以确保输入的数组是有效的。如果输入的数组为空，或者其内部的任何一行是空的，我们应该返回0，因为没有像素存在。这可以通过检查数组的长度以及每行的长度来实现。例如，可以在函数的开始处添加如下代码： python if not picture or not picture[0]: return 0 这样的检查确保了即使输入为空或非法，函数也能正确地返回一个合理的结果，从而避免了在后续代码中访问不存在的索引，这可能导致错误或异常。