计算二维子数组中的真数

Question

给定布尔值的二维数组：

{{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，取入子数组的起点和终点上面的二维数组和 return 一个布尔值，如果这个子数组至少有 1 true.

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

例如，如果我们要检查从索引 (0,0) 到 (1,1) 的区域，我们将调用 hasTrue(0,0,1,1) 并且它将 return true 因为索引 (1,0) 的值为 true。我们可以给它一个与起点相同的端点。例如，hasOnes(0,0,0,0) 这将仅检查数组的单个索引，该索引包含值 false 并且将 return false.

我需要实现一种方法来计算给定子数组中的真数，我 必须使用 hasTrue 方法。

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

一种解决方案是从开始索引到结束进行暴力破解，并计算具有 true 的索引的数量。但在最好的情况下，复杂度将是 n*m.

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

如果returns true我会拆分数组，每半检查一次，继续这样做，统计正确的个数。

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

Answer 1

我会写 C++ 代码（抱歉）忘记了 Java，但仍然可以帮助您。当然，转换为 Java 并不困难。实现了你递归分成两半的想法，实际上是分成了4个almost-equal象限(sub-rectangles).

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

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 3

为了以最有效的方式解决这个问题，我们必须考虑当hasTrue returns为真时，我们不知道有多少true；然而，当它 returns 为 false 时，我们知道我们可以丢弃整个区域，因为它的计数（以及任何子区域的计数）将始终为 0。因此我们应该从最大区域的 hasTrue 开始，并且如果 returns 为真，则划分并继续；如果 returns 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 returns 为真时，才会递归调用 countTrues。没有这个，递归实现并不比 brute-force 迭代实现更好。

Answer 4

由于你不能直接访问数组，只能通过hasTrue方法，你可以使用[=20构建递归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
}

计算二维子数组中的真数

Count the number of trues in a 2D subarray

java

arrays

algorithm

binary-search

multidimensional-array