我们得到二维矩阵数组(假设长度为 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 上做这件事
如果有人能给我任何提示,我会很高兴:)
最佳答案
首先,创建一个辅助矩阵: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))
解决方案。
关于算法 - 在矩阵中求和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35585822/