计算二维子阵列中的真实数

Question

给定布尔值的2D数组：

{{false, false, true, false, true}
{true, false, true, false, false}
{false, true, false, false, false}
{false, false, false, false, false}
{true, true, true, true, true}}

并且不能直接访问数组，必须通过现成的方法hasTrue，该方法接收上述2D数组的子数组的起点和终点，如果该子数组至少有1个true，则返回布尔值。

boolean hasTrue(int startX, int startY, int endX, int endY)

例如，如果我们想检查从索引(0,0)到(1,1)的区域，我们将调用hasTrue(0,0,1,1)，它将返回true，因为索引(1,0)具有值true。我们可以给它一个与起点相同的终点。例如，hasOnes(0,0,0,0)这将只检查数组的单个索引，该索引保持值false并将返回false。

我需要实现一个计算给定子数组中true数量的方法，并且我必须使用hasTrue方法。

int countTrues(int startX, int startY, int endX, int endY)

一种解决方案是从开始索引到结束强制执行，并计算具有true的索引的数量。但在最复杂的情况下，它将是n*m。

我正在考虑的另一个解决方案是实现一种递归方法，该方法将整个子数组同时传递给hasOnes()，如果整个子数组返回false，那么我不需要遍历所有索引，我只返回0，这将是最好的O(1)情况。

如果它返回true，我将拆分数组并每隔一半进行检查，然后继续这样做并计算true的数量。

如何实施第二个解决方案？

Answer 1

我会把C++代码(抱歉(写成忘记的Java，但仍然可以帮助您。当然，转换成Java并不困难。它实现了递归划分为两半的想法，实际上它划分为4个几乎相等的象限(子矩形(。

int countTrues(int xb, int yb, int xe, int ye) { // x/y begins/ends
if (xb > xe || yb > ye) // zero-size (empty) array
return 0;
bool h = hasTrue(xb, yb, xe, ye);
if (!h || (xb == xe && yb == ye)) // all-false or single-element array
return (h ? 1 : 0);
int xm = (xb + xe) / 2, ym = (yb + ye) / 2; // middle (center) point
return ( // sum counts of 4 almost-equal quadrants (sub-rectangles)
countTrues(xb, yb, xm, ym) +       // top-left
countTrues(xm + 1, yb, xe, ym) +   // top-right
countTrues(xb, ym + 1, xm, ye) +   // bottom-left
countTrues(xm + 1, ym + 1, xe, ye) // bottom-right
);
}

Answer 2

为了以最有效的方式解决这个问题，我们必须考虑当hasTrue返回true时，我们不知道存在多少true；然而，当它返回false时，我们知道我们可以丢弃整个区域，因为它的计数(以及任何子区域的计数(将始终为0。因此，我们应该从最大面积上的hasTrue开始，如果它返回true，则除法并继续；如果返回false，我们可以丢弃整个区域。这个的递归实现：

int countTrues(int startX, int startY, int endX, int endY) {
int count = 0;
if (endX >= startX && endY >= startY) {
int midX = (endX + startX) / 2;
int midY = (endY + startY) / 2;
// top-left
if (hasTrue(startX, startY, midX, midY)) {
count += countTrues(startX, startY, midX, midY);
}
// top-right
if (hasTrue(midX + 1, startY, endX, midY)) {
count += countTrues(midX + 1, startY, endX, midY);
}
// bottom-left
if (hasTrue(startX, midY + 1, midX, endY)) {
count += countTrues(startX, midY + 1, midX, endY);
}
// bottom-right
if (hasTrue(midX + 1, midY + 1, endX, endY)) {
count += countTrues(midX + 1, midY + 1, endX, endY);
}
}
return count;
}

该实现中的重要元素是，只有当hasTrue在特定子区域上返回true时，才有对countTrues的递归调用。如果没有这一点，递归实现并不比暴力迭代实现好。

Answer 3

countTrues函数可以使用递归实现，基本上你从水平将数组一分为二开始，当只剩下一行时，垂直将其一分为二，很容易理解：

int countTrues(int startX, int startY, int endX, int endY) {
if (!hasTrue(startX, startY, endX, endY)) return 0;
if (startX < endX) {
//split horizontally
return countTrues(startX, startY, (startX + endX) / 2, endY) +
countTrues((startX + endX) / 2 + 1, startY, endX, endY);
} else if (startY < endY) {
//split vertically
return countTrues(startX, startY, endX, (startY + endY) / 2) +
countTrues(startX, (startY + endY) / 2 + 1, endX, endY);
}
//only one value left and is true
return 1;
}

这里有一个完整的解决方案：

public class Main {
static boolean array[][] = {
{false, false, true, false, true},
{true, false, true, false, false},
{false, true, false, false, false},
{false, false, false, false, false},
{true, true, true, true, true}};
public static void main(String[] args) {
int rowLen = array.length, colLen = array[0].length;
int res = countTrues(0, 0, rowLen - 1, colLen - 1);
System.out.println("number of Trues: " + res);
}
static boolean hasTrue(int startX, int startY, int endX, int endY) {
while (startX <= endX) {
int indexY = startY;
while (indexY <= endY) {
if (array[startX][indexY]) return true;
indexY++;
}
startX++;
}
return false;
}
static int countTrues(int startX, int startY, int endX, int endY) {
if (!hasTrue(startX, startY, endX, endY)) return 0;
if (startX < endX) {
//split horizontally
return countTrues(startX, startY, (startX + endX) / 2, endY) +
countTrues((startX + endX) / 2 + 1, startY, endX, endY);
} else if (startY < endY) {
//split vertically
return countTrues(startX, startY, endX, (startY + endY) / 2) +
countTrues(startX, (startY + endY) / 2 + 1, endX, endY);
}
//only one value left and is true
return 1;
}
}

Answer 4

由于不能直接访问数组，只能通过hasTrue方法，因此可以使用半除法方法构建递归countTrues方法。您可以使用IntStream来迭代：

static boolean[][] arr = {
{false, false, true, false, true},
{true, false, true, false, false},
{false, true, false, false, false},
{false, false, false, false, false},
{true, true, true, true, true}};

static boolean hasTrue(int startX, int startY, int endX, int endY) {
// invalid syntax
if (startX > endX || startY > endY)
return false;
return IntStream
// iterate over specified
// range of the rows
.rangeClosed(startX, endX)
// get row by index
// Stream<boolean[]>
.mapToObj(i -> arr[i])
// at least one true in any row
.anyMatch(row -> IntStream
// iterate over specified
// range of the elements
.rangeClosed(startY, endY)
// at least one true in the row
.anyMatch(j -> row[j]));
}

static int countTrues(int startX, int startY, int endX, int endY) {
// no trues on this iteration
if (!hasTrue(startX, startY, endX, endY))
return 0;
// recursive calls
int lengthX = endX - startX;
int lengthY = endY - startY;
int middleX = lengthX / 2;
int middleY = lengthY / 2;
if (lengthX > 0 || lengthY > 0)
return IntStream
// if 'lengthX > 0' then two iterations X:
// from beginning to middle and from
// middle to end, otherwise one iteration
.rangeClosed(0, lengthX > 0 ? 1 : 0)
.map(i -> i == 0 ? 0 : middleX + 1)
.map(i -> IntStream
// if 'lengthY > 0' then two iterations Y:
// from beginning to middle and from
// middle to end, otherwise one iteration
.rangeClosed(0, lengthY > 0 ? 1 : 0)
.map(j -> j == 0 ? 0 : middleY + 1)
// recursive calls, if it is necessary for
// top-left, top-right, bottom-left, bottom-right
.map(j -> countTrues(startX + i, startY + j,
i == 0 ? startX + middleX : endX,
j == 0 ? startY + middleY : endY))
.sum())
.sum();
// if it reached this point, this point is true
return 1;
}

public static void main(String[] args) {
System.out.println(hasTrue(1, 1, 3, 3)); // true
System.out.println(countTrues(1, 1, 3, 3)); // 2
}