algorithm - 在 log(n) 时间内排序的 bool n*n 矩阵中 0 的数量

Question

这是一道谷歌面试题。

给定一个 N 行 N 列的矩阵。矩阵中的元素可以是 1 或 0。矩阵的每一行和每一列都按升序排序。找出给定矩阵中 0 的个数。

我想出了一个 O(n) 的解决方案，但根本无法提出一个 O(logn) 的解决方案。非常感谢任何指点。

编辑:O(logn) 似乎是不可能的，如下所述。

Answer 1

首先，这是一个在 O(n) 时间内计算零的算法:

countZeroes(matrix):
    n = matrix.rowCount
    i = 0
    j = n-1
    count = 0
    while i < n && j >=0:
        if matrix[i][j] == 1 then:
            j--
        else:
            i++
            count += j+1
    return count

因为每次迭代都会增加 i 或减少 j，并且两者只能在循环之前取 0..n-1 之间的值结束，最大迭代次数为2n，即O(n)。

这是一个生成 5x5 随机矩阵并使用上述算法计算零的 JavaScript 片段:

    function countZeroes(matrix) {
        var n = matrix.length,
            i = 0,
            j = n-1,
            count = 0;
        while (i < n && j >=0) {
            if (matrix[i][j] === 1) {
                j--;
            } else {
                i++;
                count += j+1;
            }
        }
        return count;
    }

    function randomMatrix(n) {
        var matrix = [],
            zeroCounts = [];
        for (var i = 0; i < n; i++) {
            zeroCounts[i] = Math.floor(Math.random() * (n+1));
        }
        zeroCounts.sort((a,b) => b-a); // descending
        for (var i = 0; i < n; i++) {
            matrix[i] = [];
            for (var j = 0; j < n; j++) {
                matrix[i][j] = j < zeroCounts[i] ? 0 : 1;
            }
        }
        return matrix;
    }

    function matrixToString(matrix) {
        var s = '';
        for (var i = 0; i < matrix.length; i++) {
            s += matrix[i].join('') + '\n';
        }
        return s;
    }

    var matrix = randomMatrix(5);
    console.log(matrixToString(matrix));
    console.log('Zeroes: ', countZeroes(matrix));

可以在 O(log n) 内完成吗？

想象这样一个矩阵:

0000
0001
0011
0111

您需要访问此矩阵中的每一行才能知道其中有多少个零。想象一下，您将只访问 4 行中的 3 行:它可以是任意 3 行……除非您还访问第四个，否则零的总数仍然至少有三种可能的结果。

例如，如果您访问了第 0 行、第 1 行和第 3 行，您会知道:

0000
0001
****
0111

根据行和列的排序，可以推导出:

0000
0001
0**1
0111

但剩余的**可能是00、01或11。找出答案的唯一方法是实际查看该行中的至少一个值。

结论:小于O(n)是不可能的。