算法 - 在矩阵中求和

Question

我们得到二维矩阵数组(假设长度为 i 和宽度为 j)和整数 k我们必须找到包含这个或更大总和的最小矩形的大小F.e k=7

4 1
1 1
1 1
4 4

Anwser是2，因为4+4=8 >= 7，如果没有最后一行，anwser就是4，4+1+1+1 = 7 >= 7

我的想法是计算前缀和 Pref[k,l]=Tab[k,l]+Pref[k-1,l]+Pref[k,l-1]然后比较每一个矩形

这有可能让它更快吗？我的想法是 T(n)=O(n^2) (其中 n 是矩阵中元素的数量)我想在时间 n 或 n * log n 上做这件事

如果有人能给我任何提示，我会很高兴:)

Answer 1

首先，创建一个辅助矩阵:sums，其中:

sums[i,j] = A[0,0] + A[0,1] + .... + A[0,j] + A[1,0] + ... + A[1,j] + ... + A[i,j]

我认为这就是您所说的“前缀矩阵”的意思。

这可以用动态规划以线性时间计算:

sums[0,j] = A[0,0] + ... + A[0,j]
sums[i,0] = A[0,0] + ... + A[i,0]
sums[i,j] = sums[i-1,j] + sums[i,j-1] - sums[i-1,j-1] + A[i,j]
                                            ^
                                     elements counted twice

现在，假设所有元素都是非负数，这是一个非递减矩阵，其中每一列和每一行都已排序。

因此，再次迭代矩阵，对于每对索引 i,j，找到最接近但小于 sum[i,j]-k 的值。

This can be done in O(sqrt(n)) .

对每个这样的 (i,j) 对执行此操作，您将得到 O(n*sqrt(n)) 解决方案。