如何在0-1矩阵中找到至少具有K 1的最小子矩形 [英] How to find minimal subrectangle with at least K 1's in a 0-1 matrix

问题描述

我遇到了一个不常见的问题，给定一个NxM 0-1矩阵和一个数K(<= NxM)，我必须找到那个0-1矩阵的最小子矩形区域，并且其中至少有K 1个下矩形.此外，应将其面积(两个维度的乘积)最小化.

I have encountered an inoridinary problem that given a NxM 0-1 matrix and a number K(<=NxM) and I have to find a minimal subrectangle area of that 0-1 matrix with at least K 1's in inside that subrectangle. Furthermore it's area(the product of both dimensions) should be minimized.

例如:
00000
01010
00100
01010
00000
K = 3

因此，我可以找到最小面积为6的子矩形，其中包含3 1的内部.
10
01
10

请注意，我指的目标子矩形应该包含原始0-1矩阵中连续的行和列数.

For example:
00000
01010
00100
01010
00000
K = 3

So I can find a subrectangle with minimal area 6 that contains 3 1's inside.
10
01
10

NOTE that the target subrectangle that I mean should contains consecutive numbers of rows and columns from the original 0-1 matrix.

推荐答案

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)).

Time complexity is O(NM(N+M)).

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

Two nested loops may be optimized by changing linear search to binary search (to process skinny sub-rectangles faster).

还可以(在向子矩形添加行/列之后)减少O(1)时间，以使该子矩形的面积不大的方式增加列/行的数量比迄今为止最好的子矩形的面积大.

Also it is possible (after adding a row/a column to the sub-rectangle) to decrease in O(1) time the number of columns/rows in such a way that the area of this sub-rectangle is not larger than the area of the best-so-far sub-rectangle.

这两个优化都需要计算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].

Both these optimizations require calculation of any sub-rectangle weight in O(1). To make it possible, pre-calculate cumulative sum of all elements for sub-rectangles [1..i,1..j] (X[i,j]). Then the weight of any sub-rectangle [i..m,j..n] is computed as 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).

Time complexity is O(N²M).

当在其内部处理的所有子矩形均为单列子矩形(行太多)时，或者当在其内部处理的所有子矩形都没有包含足够的一个"时，"l"循环可能会终止.没有足够的行.

Loop by 'l' may be terminated when all sub-rectangles, processed inside it, are single-column sub-rectangles (too many rows) or when no sub-rectangles, processed inside it, contain enough "ones" (not enough rows).

这篇关于如何在0-1矩阵中找到至少具有K 1的最小子矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！