gpt4 book ai didi

algorithm - 找到包含最多 "conflicting pairs"的 m 乘 m 方格?

转载 作者:行者123 更新时间:2023-12-03 08:25:23 26 4
gpt4 key购买 nike

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

如果两个单元的颜色不同,则称为“冲突对”。目标是找到包含最多“冲突对”的 m 乘 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×n 矩阵可能很大且稀疏,并且以稀疏格式(如 CSR)给出,在这种情况下,O(n^2) 算法可能效率不高。关于如何更好地处理稀疏矩阵(和密集矩阵)的任何建议?

最佳答案

如果您有 k 个非空单元格(使用 RG),那么您可以用时间复杂度 O( k^2)(压缩矩阵)因为最优子矩阵在矩阵的边界上有一个非空单元格。

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

关于algorithm - 找到包含最多 "conflicting pairs"的 m 乘 m 方格?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59569132/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com