C++ 中的孤独像素 II

孤独像素 II 问题是寻找二维字符网格中特定的黑色像素（'B'）。网格包含两种类型的像素：黑色（'B'）和白色（'W'）。如果一个黑色像素满足两个条件，则称其为孤独像素：

• 它是其所在行的唯一黑色像素。
• 它是其所在列的唯一黑色像素。

目标是计算网格中孤独黑色像素的总数。

输入示例

例如，考虑以下网格：

在这个网格中：

• 每个黑色像素（'B'）都是其所在行和列的唯一黑色像素。因此，所有三个黑色像素都是孤独的。

解决问题的步骤

为了高效地解决这个问题，请按照以下步骤进行：

步骤 1：计算行和列中的黑色像素数量

首先，计算每一行和每一列中黑色像素的数量。这些信息有助于我们快速确定一个黑色像素是否是孤独的。

例如，在网格中：

行计数

• 第0行：1个黑色像素。
• 第1行：1个黑色像素。
• 第2行：1个黑色像素。

列计数

• 第0列：1个黑色像素。
• 第1列：1个黑色像素。
• 第2列：1个黑色像素。
• 第3列：0个黑色像素。

步骤 2：检查每个黑色像素

对于网格中的每个黑色像素：

1. 检查它是否是其所在行的唯一黑色像素。
2. 检查它是否是其所在列的唯一黑色像素。

如果两个条件都成立，则它是一个孤独像素。

方法 1：简单方法

程序

输出

Number of Lonely Pixels: 3   

1. 理解输入

输入是一个由字符 'B' 和 'W' 组成的二维网格或矩阵。

• 'B' 代表黑色像素。
• 'W' 代表白色像素。

我们的目标是找到孤独黑色像素的数量。黑色像素是孤独的，如果：

• 它是其所在行的唯一黑色像素。
• 它是其所在列的唯一黑色像素。

例如

在这里，所有黑色像素都是孤独的，因为它们中的每一个都是其各自行和列中唯一的 'B'。

2. 如何处理这个问题

要找到孤独的黑色像素，我们需要：

• 计算每一行中的黑色像素数量。
• 计算每一列中的黑色像素数量。
• 对于网格中的每个 'B' 进行检查：
• 如果其所在行只有 1 个 'B'。
• 如果其所在列只有 1 个 'B'。

如果两个条件都成立，则该像素是孤独的，我们对其进行计数。

3. 代码分步解释

步骤 1：计算黑色像素

我们创建两个列表（或数组）：

• rowCount 用于存储每一行中 'B' 的数量。
• colCount 用于存储每一列中 'B' 的数量。

然后我们逐个单元地遍历整个网格：

• 如果当前单元格包含 'B'，我们会增加该行和该列的计数。

例如，如果网格是：

计数后：

rowCount 变为 [1, 1, 1]，因为每一行都有 1 个 'B'。

colCount 变为 [1, 1, 1, 0]，因为：

• 第0列有 1 个 'B'。
• 第1列有 1 个 'B'。
• 第2列有 1 个 'B'。
• 第3列没有 'B'。

步骤 2：检查每个像素

接下来，我们再次遍历网格。对于每个单元格：

如果它包含 'B'：

• 在 rowCount 中检查其行计数。
• 在 colCount 中检查其列计数。

如果行和列的计数都为 1，这意味着这个 'B' 是孤独的。

例如

第0行、第0列的第一个 'B' 是孤独的，因为：

• rowCount[0] = 1（其所在行只有一个黑色像素）。
• colCount[0] = 1（其所在列只有一个黑色像素）。

同样，其他黑色像素也是孤独的。

步骤 3：计算孤独像素

每次找到一个孤独像素，我们都会增加一个计数器（lonelyCount）。在过程结束时，计数器将给出网格中孤独黑色像素的总数。

4. 效率

这个解决方案很高效，因为：

1. 它只遍历网格两次：
   • 一次用于计算行和列的计数。
   • 第二次用于检查孤独像素。
2. 它使用了两个数组（rowCount 和 colCount）来跟踪计数，这比反复重新计算计数节省了时间。

5. 示例演练

让我们回顾一下这个网格：

步骤 1（计算黑色像素）

• rowCount = [1, 1, 1]（每行一个 'B'）。
• colCount = [1, 1, 1, 0]（第0、1、2列有一个 'B'，第3列没有）。

步骤 2（检查孤独像素）

第一个 'B' 在 (0, 0)

• rowCount[0] = 1（第0行只有一个 'B'）。
• colCount[0] = 1（第0列只有一个 'B'）。
• 它是孤独的。

第二个 'B' 在 (1, 1)

• rowCount[1] = 1（第1行只有一个 'B'）。
• colCount[1] = 1（第1列只有一个 'B'）。
• 它是孤独的。

第三个 'B' 在 (2, 2)

• rowCount[2] = 1（第2行只有一个 'B'）。
• colCount[2] = 1（第2列只有一个 'B'）。
• 它是孤独的。

步骤 3（计算孤独像素）

• 孤独像素总数 = 3。

6. 最终输出

对于给定的示例网格，孤独黑色像素的数量是 3。

方法 2：使用 Map 跟踪行和列

与使用固定大小的 数组 来存储 rowCount 和 colCount 不同，我们可以使用哈希表（Map）来动态跟踪行和列中黑色像素的数量。当网格稀疏或网格尺寸非常大时，这种方法尤其有用。

程序

输出

Number of Lonely Pixels: 3   

说明

使用的数据结构

• 两个哈希表（rowCount 和 colCount）用于跟踪每一行和每一列中黑色像素 ('B') 的数量。
• 一个列表（blackPixels）用于存储所有黑色像素的位置。

第一次遍历网格

• 代码逐行扫描网格。
• 每次找到 'B' 时：
• 增加 rowCount 中该行的计数。
• 增加 colCount 中该列的计数。
• 将位置（行，列）保存在 blackPixels 中。

第二次使用 blackPixels 进行遍历

• 对于 blackPixels 中存储的每个位置：
• 在 rowCount 中检查相应的行计数。
• 在 colCount 中检查相应的列计数。
• 如果两个计数都为 1，则表示该黑色像素是孤独的。

计算孤独像素

• 在第二次遍历中找到的每个孤独黑色像素，都会使计数器（lonelyCount）加一。

输出

• lonelyCount 的最终值将是网格中孤独黑色像素的总数。

示例演练

对于网格：

1. 第一次遍历后：
   • rowCount: {0: 1, 1: 1, 2: 1}。
   • colCount: {0: 1, 1: 1, 2: 1}。
   • blackPixels: [(0, 0), (1, 1), (2, 2)]。
2. 在第二次遍历中：
   • (0, 0) 的 rowCount[0] = 1 且 colCount[0] = 1 → 孤独。
   • (1, 1) 的 rowCount[1] = 1 且 colCount[1] = 1 → 孤独。
   • (2, 2) 的 rowCount[2] = 1 且 colCount[2] = 1 → 孤独。
3. 最终 lonelyCount = 3。

复杂度分析

时间复杂度

第一次遍历： O(m×n)

• 扫描网格中的每个单元格以计数黑色像素并记录其位置。

第二次遍历： O(k)

• 检查 blackPixels 列表中的每个黑色像素，其中 k 是黑色像素的数量。

总计： O(m×n)，因为 k≤m×n。

空间复杂度

行和列的 Map： O(m+n)，用于存储计数。

黑色像素位置： O(k)。

总计： O(m+n+k)。

方法 3：不使用额外数据结构的行和列迭代

无需使用 Map 或数组来跟踪计数，我们可以在遍历网格时直接计算计数。这种方法避免了使用额外的存储空间来存放行和列的计数。

程序

输出

Number of Lonely Pixels: 3   

说明

网格遍历

• 程序逐行逐列地循环遍历网格中的每个单元格。
• 对于每个单元格，它会检查值是否为 'B'（黑色像素）。如果不是 'B'，则继续下一个单元格。

计算行中的黑色像素数量

• 一旦在特定位置 (i, j) 找到黑色像素，程序就会计算该行中的所有黑色像素。
• 它通过遍历该行的所有列并保持一个计数器（rowBlackCount）来实现这一点。
• 如果该行中的黑色像素数量大于 1，则当前黑色像素不可能是孤独的，因此会跳过对该像素的进一步检查。

计算列中的黑色像素数量

• 如果行计数恰好为 1，程序会继续计算当前位置 (i, j) 所在列中的所有黑色像素。
• 它通过遍历该列的所有行并保持另一个计数器（colBlackCount）来实现这一点。
• 如果列计数大于 1，则当前黑色像素不可能是孤独的，因此不会计入最终计数。

检查孤独性

• 当满足以下条件时，黑色像素被认为是孤独的：
• 其所在行中的黑色像素总数为 1。
• 其所在列中的黑色像素总数为 1。
• 如果两个条件都满足，程序会增加孤独黑色像素的计数器（lonelyCount）。

最终计数

• 检查完网格中的所有单元格后，程序将得到所有孤独黑色像素的总数。
• 这个计数将作为结果输出。

示例演练

给定网格：

步骤 1：从 (0, 0) 开始

• 找到 'B'。
• 计算第0行中的黑色像素：1个黑色像素 ('B')。
• 计算第0列中的黑色像素：1个黑色像素 ('B')。
• 两个计数都为 1 → 找到一个孤独像素。

步骤 2：移动到 (0, 1)

• 找到 'W'，跳过此单元格。

步骤 3：继续到 (1, 1)

• 找到 'B'。
• 计算第1行中的黑色像素：1个黑色像素 ('B')。
• 计算第1列中的黑色像素：1个黑色像素 ('B')。
• 两个计数都为 1 → 找到一个孤独像素。

步骤 4：继续到 (2, 2)

• 找到 'B'。
• 计算第2行中的黑色像素：1个黑色像素 ('B')。
• 计算第2列中的黑色像素：1个黑色像素 ('B')。
• 两个计数都为 1 → 找到一个孤独像素。

最终计数

• 孤独像素 = 3。

复杂度分析

外层循环

• 遍历网格中的每个单元格 → O(m×n)。

每个黑色像素的行计数

• 计算一行中的黑色像素 → 每个黑色像素 O(n)。

每个黑色像素的列计数

• 计算一列中的黑色像素 → 每个黑色像素 O(m)。

总时间

• 对于 k 个黑色像素，时间 = O(k×(m+n))。
• 最坏情况，k=m×n → O(m×n×(m+n))。

空间复杂度

额外存储

• 没有额外的数据结构 → O(1) 额外空间。

网格存储

• 网格已提供 → O(m×n)。

优点

C++ 中的孤独像素 II 有几个优点，如下所示：

简单性

• 该方法易于理解和实现，因为它直接遍历网格并即时计算像素，而无需复杂的 数据结构。

无额外空间（高效的空间利用）

• 该算法使用 O(1) 的额外空间，这意味着它不需要额外的数组或哈希表来存储行和列的计数。它只使用几个变量进行计数。

无排序

• 与其他一些方法不同，该方法不需要排序或复杂的算法，对于大小适中的网格来说非常简单。

缺点

C++ 中的孤独像素 II 有几个缺点，如下所示：

重复计数

• 该算法对每个黑色像素重复计算同一行和同一列中的黑色像素，导致不必要的冗余计算。

不适用于大型网格

• 对于大型网格，此方法可能很慢，因为它对每个像素执行了许多不必要的检查。