java - 计算二维子数组中的真数

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，接受上述二维数组的子数组的起点和终点，如果这个子数组至少有 1 ，则返回一个布尔值true。

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

例如，如果我们想检查从 index(0,0)到(1,1)我们将调用的区域hasTrue(0,0,1,1)，它会返回true，因为 index(1,0)具有 value true。我们可以给它与开始相同的端点。例如，hasOnes(0,0,0,0)这将仅检查数组的单个索引，该索引包含值false并将返回false。

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

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

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

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

如果它返回true，我将拆分数组并检查每一半，并继续这样做并计算真数。

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

标签： javaarraysalgorithmmultidimensional-arraybinary-search

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
    );
}