algorithm - 如何在 0-1 矩阵中找到至少有 K 个 1 的最小子矩形

Question

我遇到了一个非常规问题，给定一个 NxM 0-1 矩阵和一个数字 K(<=NxM)，我必须找到该 0-1 矩阵的最小子矩形区域，该子矩形内至少有 K 个 1 .此外，它的面积(两个维度的乘积)应该最小化。

例如:
00000
01010
00100
01010
00000
K = 3

所以我可以找到一个最小面积为 6 的子矩形，其中包含 3 个 1。
10
01
10

请注意，我的意思是目标子矩形应该包含来自原始 0-1 矩阵的连续行数和列数。

Answer 1

Compute cumulative sum of rows R[i,j] and columns C[i,j].
For top-left corner (i,j) of each possible sub-rectangle:
   Starting from a single-row sub-rectangle (n=i),
   Search the last possible column for this sub-rectangle (m).
   While m>=j:
     While there are more than 'k' "ones" in this sub-rectangle:
       If this is the smallest sub-rectangle so far, remember it.
       Remove column (--m).
       This decreases the number of "ones" by C[m+1,n]-C[m+1,j-1].
     Add next row (++n).
     This increases the number of "ones" by R[m,n]-R[i-1,n].

时间复杂度为 O(NM(N+M))。

可以通过将线性搜索更改为二进制搜索来优化两个嵌套循环(以更快地处理瘦子矩形)。

也有可能(在向子矩形添加一行/一列之后)在 O(1) 时间内减少列/行的数量，使得该子矩形的面积不会变大比迄今为止最好的子矩形的面积。

这两种优化都需要在 O(1) 中计算任何子矩形权重。为了使其成为可能，预先计算子矩形 [1..i,1..j] (X[i,j]) 的所有元素的累积和。然后任何子矩形 [i..m,j..n] 的权重被计算为 X[m,n]-X[i-1,n]-X[m,j-1]+ X[i-1,j-1].

---

Compute cumulative sum of columns C[i,j].
For any starting row (k) of possible sub-rectangle:
  For any ending row (l) of possible sub-rectangle:
    Starting column (m = 1).
    Ending column (n = 1).
    While n is not out-of-bounds
      While there are less than 'k' "ones" in sub-rectangle [k..l,m..n]:
        Add column (++n).
        This increases the number of "ones" by C[l,n]-C[k-1,n].
      If this is the smallest sub-rectangle so far, remember it.
      Remove column (++m).
      This decreases the number of "ones" by C[l,m-1]-C[k-1,m-1].

时间复杂度为 O(N²M)。

如果在其中处理的所有子矩形都是单列子矩形(行太多)，或者在其中处理的子矩形中没有包含足够的“一”(没有足够的行)。