如何高效实现矩阵2x2窗口扫描以统计1比特频率？

现有列前缀和思路的局限 #

你提到的列1比特数数组优化（本质是列前缀和）确实能把窗口计数的时间从O(4*(行数-1)(列数-1))降到O((行数-1)(列数-1))，但如果已知所有1的坐标，我们可以用更高效的反向统计思路，尤其是当矩阵里1的数量远小于总元素数时，优势会非常明显。

最优方案：基于1坐标的反向贡献统计 #

既然已经知道所有1的[r,c]坐标，我们可以反过来算每个1会给哪些2x2窗口加1，最后统计每个窗口的总1数，再生成频率数组：

• 初始化一个window_counts数组，大小为(行数-1)*(列数-1)，所有元素初始为0；再初始化长度为5的freq数组（因为2x2窗口最多4个1），初始全0。
• 遍历每个1的坐标(r,c)：
  • 这个1能覆盖的合法2x2窗口是左上角为(r-1,c-1)、(r-1,c)、(r,c-1)、(r,c)的窗口，但要保证窗口左上角的行在0~行数-2范围内，列在0~列数-2范围内。
  • 对每个合法的窗口位置(wr, wc)，把window_counts[wr*(列数-1)+wc]加1。
• 最后遍历window_counts，把每个数值的出现次数对应填入freq数组即可。

复杂度对比 #

假设矩阵里总共有k个1，这个方法的时间复杂度是O(k + (行数-1)(列数-1))。当k远小于矩阵总元素数时，比列前缀和的O(行数列数)要快得多——比如稀疏矩阵场景，k可能只有几十，但矩阵是1000x1000的，这种差距会非常大。

测试用例验证 #

拿你给的测试用例来看：
矩阵是3行4列，1的坐标是(0,0),(0,3),(1,1),(1,3),(2,0),(2,3)
逐个处理每个1：

• (0,0)：只影响窗口(0,0) → window_counts[0] +=1
• (0,3)：只影响窗口(0,2) → window_counts[2] +=1
• (1,1)：影响窗口(0,0)和(0,1) → window_counts[0] +=1，window_counts[1] +=1
• (1,3)：影响窗口(0,2)和(1,2) → window_counts[2] +=1，window_counts[5] +=1
• (2,0)：只影响窗口(1,0) → window_counts[3] +=1
• (2,3)：只影响窗口(1,2) → window_counts[5] +=1

最终window_counts是[2,1,2,1,0,2]，统计后得到freq[1]=2，freq[2]=4，其他为0，和预期结果一致。

备选优化：滑动窗口实时更新 #

如果没法提前拿到所有1的坐标（比如矩阵是流式加载的），可以用滑动窗口实时更新的方式：

1. 先算第一个窗口（左上角(0,0)）的1数：直接统计4个位置的和。
2. 同一行内窗口右滑时，减去窗口左边缘两格的1数，加上窗口右边缘新进入的两格的1数，就能快速得到新窗口的总数。
3. 一行处理完后，窗口下移一行：减去窗口上边缘两格的1数，加上窗口下边缘新进入的两格的1数，再重复右滑操作。

这种方法不需要额外存前缀和数组，空间复杂度更低，时间复杂度也是O(行数*列数)，适合稠密矩阵场景。

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