数组中的矩形区域

Question

给定一个 N*N 矩阵，其中包含 1 和 0，并且给定一个整数 k，找到其中包含 k 个 1 的矩形区域的最佳方法是什么？？？

Answer 1

我可以用 O(N^3*log(N)) 来完成，但肯定最好的解决方案更快。首先创建另一个 N*N 矩阵 B（初始矩阵是 A）。 B 的逻辑如下：

B[i][j] - is the number of ones on rectangle in A with corners (0,0) and (i,j).

您可以通过动态规划以 O(N^2) 计算 B： B[i][j] = B[i-1][j] + B[i][j-1] - B[i-1][j-1] + A[i][j]。

现在，通过迭代所有右下 (i=1..N, j=1..N, O(N^2))、左下 ( z=1..j, O(N)) 和右上 (t=1..i, O(N)) 并在 B 的帮助下得到这个矩形中 1 的数量：

sum_of_ones = B[i][j] - B[i][z-1] - B[t-1][j] + B[t-1][z-1].

如果你正好得到k: k==sum_of_ones，然后输出结果。

为了使其成为 N^3*log(N)，您应该通过二分搜索找到右上（所以不仅仅是迭代所有可能的单元格）。

Answer 2

考虑这个更简单的问题：

给定一个大小为 N 且仅包含值 1 和 0 的向量，找到一个恰好包含 k 个值 1 的子序列。

令 A 为给定向量，并且 S[i] = A[1] + A[2] + A[3] + ... + A[i]，表示子序列A[1..i]中有多少个1。

对于每个 i，我们感兴趣的是 j <= i 是否存在，使得 S[i] - S[j-1] == k。

我们可以使用以下关系在 O(n) 中通过哈希表找到它：

S[i] - S[j-1] == k => S[j-1] = S[i] - k

let H = an empty hash table
for i = 1 to N do
  if H.Contains (S[i] - k) then your sequence ends at i
  else
    H.Add(S[i])

现在我们可以用它来解决 O(N^3) 中给定的问题：对于给定的每个行序列矩阵（有 O(N^2) 行序列），考虑该序列来表示向量并对其应用之前的算法。在矩阵情况下，S 的计算有点困难，但并不难算出来。如果您需要更多详细信息，请告诉我。

更新：
以下是该算法如何处理以下矩阵，假设 k = 12：

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

单独考虑第一行：

0 1 1 1 1 0

将其视为向量 0 1 1 1 1 0 并应用更简单问题的算法：我们发现没有子序列加起来等于 12，所以我们继续。

考虑前两行：

0 1 1 1 1 0
0 1 1 1 1 0

将它们视为向量 0+0 1+1 1+1 1+1 1+1 0+0 = 0 2 2 2 2 0 并应用算法更简单的问题：同样，没有子序列加起来等于 12，所以继续。

考虑前三行：

0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0

将它们视为向量 0 3 3 3 3 0 并对其应用更简单问题的算法：我们找到从位置 2 开始并在位置 5 结束的序列成为解决方案。由此我们可以通过简单的记账得到整个矩形。