时间戳

首页 > 解决方案 > 找到包含最多“冲突对”的 m x m 方格？

algorithm - 找到包含最多“冲突对”的 m x m 方格？

问题描述

二维平面上有两种类型的单位，绿色单位 (G) 和红色单位 (R)。平面表示为 n × n 矩阵，每个单元表示为矩阵中的一个元素。

如果两个单元的颜色不同，则一对两个单元称为“冲突对”。目标是找到包含最多“冲突对”的 m x m 子矩阵。

例子

[R R 0 0 0
 R R 0 0 0
 0 0 R R 0
 0 0 0 G G
 0 0 0 G G]

在上面的 5×5 矩阵中，“最冲突”的 3×3 子矩阵在右下角，其中有两个红色单元和四个绿色单元，在子矩阵内总共有 8 个冲突对。

一个简单的解决方案将采用 O(m^2n^2) 来迭代每个可能的子矩阵中的每个元素。我还考虑过使用像Summed-area table算法这样的动态编程，时间复杂度将是 O(n^2)，这看起来不错，因为扫描每个元素一次已经是 O(n^2)。

但是，n x n 矩阵可能很大且稀疏，并且以稀疏格式（如 CSR）给出，在这种情况下，O(n^2) 算法可能效率不高。关于如何更好地处理稀疏矩阵（和密集矩阵）的任何建议？

标签： algorithmsparse-matrix

解决方案

如果您有k非空单元格（使用R或G），那么您可以使用时间复杂度求解O(k^2)（挤压矩阵），因为最优子矩阵在矩阵的边界上有一个非空单元格。

或者时间复杂度可能O(k * (log n)^2)是如果使用二维稀疏线段树来获取矩形的总和。

推荐阅读