如何在O(n²)时间内对n×n二进制矩阵执行指定重复操作？

问题背景 #

给定一个n×n的二进制矩阵，允许执行以下三类操作，需重复应用直到无法再执行为止，要求整体时间复杂度控制在O(n²)：

1. 将恰好包含1个孤立1的行置零；
2. 将恰好包含1个孤立1的列置零；
3. 将存在完全副本的行置零。

实现思路与步骤 #

1. 用计数追踪孤立1的快速处理 #

• 先预处理统计每一行、每一列的1的数量，得到row_counts（长度n）和col_counts（长度n），这一步耗时O(n²)。
• 维护一个队列来跟踪当前需要处理的行/列（初始时把所有row_counts[i] == 1的行i、col_counts[j] == 1的列j加入队列）：
  • 处理队列中的行i：找到该行唯一的1的位置(i,j)，将整行置零，同时把col_counts[j]减1。如果col_counts[j]变为1，就把列j加入队列等待处理。
  • 处理队列中的列j：找到该列唯一的1的位置(i,j)，将整列置零，同时把row_counts[i]减1。如果row_counts[i]变为1，就把行i加入队列等待处理。
• 注意：每个1最多被置零一次，因此这部分的累计操作总耗时是O(n²)（矩阵总元素数固定）。

2. 重复行的高效去重处理 #

当队列中没有待处理的行/列时，处理重复行：

• 为每行计算一个唯一哈希值（比如把二进制行转换为整数，或者用滚动哈希），计算所有行哈希的时间是O(n²)。
• 遍历哈希值，把相同哈希的行归为一组。每组中除保留一行外，其余行全部置零。
• 置零重复行时，逐列更新col_counts：对于被置零行中原本为1的位置(i,j)，将col_counts[j]减1。如果减1后col_counts[j] == 1，就把列j加入队列，触发后续的孤立1处理。

3. 循环迭代直到稳定 #

由于重复行置零可能产生新的孤立列，孤立列处理又可能产生新的孤立行或重复行，需要循环执行以下流程直到无操作可执行：

• 优先处理队列中的所有孤立行/列，更新矩阵和计数；
• 若队列空，处理重复行，更新矩阵和计数，并将新产生的孤立列加入队列。

时间复杂度验证 #

• 初始化计数：O(n²)
• 孤立1处理：每个元素最多被修改一次，累计元素修改量是O(n²)，计数更新为常数时间，总耗时O(n²)。
• 重复行处理：哈希计算和置零操作的累计元素处理量也是O(n²)，且重复行处理的次数有限（每次处理后被置零的行不会再参与后续重复判断），总耗时O(n²)。

整体流程的时间复杂度为O(n²)，满足要求。

内容的提问来源于stack exchange，提问作者Simd