在3n−⌊lg n⌋−3中的二元矩阵中找到所需的索引

Question

给出了一个n×n矩阵M，其中每个条目都是0或1。给出了确定∃i，1≤i≤n，使得Mi，j=0和Mj，i= 1，∀j，1≤j≤n∧j!=i的算法。您的算法最多必须检查M的3n−⌊lg n⌋−3条目。

提示：将‘检查Mi，j’与比较i和j‘联系起来。最初，每个索引都可能是所需的索引i。将潜在索引i的数目从n消除为1。然后验证该索引是否确实是所需的索引i。

有聪明的人在外面遮挡更多的灯光或暗示解决这个问题吗？我在这个领域是新的，任何出现在我脑海中的方法都以O(n^2)结尾。有什么建议吗？

我考虑了一些寻找模式的基本案例：

• 2×2矩阵M，将每个条目作为比较，则有4-2(对角线elts) =2比较.如果我们用期望的运行时间T(n) -3 = 3*2 - comparisons
• 4-by -3 =3*2- lg2 -3 =2
• 3 -by 3 M，9(条目)-3(对角线等)=6比较，期望T(n) = 3*3层(Lg3)-3= 9-4=5 lg2 4将进行16-4 = 12比较，T(n) =3×4- lg4 -3= 12-5 =7比较，我们在这里观察到一个很大的差异和想法崩溃。但是如果我能找到对矩阵条目的方法，那我就很好了。上述基本情况将减少到1、3和6种比较，并将保持在T(N)中。

接下来，我想把这个问题归结为证明M是对称的还是不对称的，这意味着存在i，使得Mij != Mji (或Mij = Mji)满足条件，因为M是二进制的。我的想法是看我是否能在线性时间内证明或否定它，但我还没有找到一个算法。

Answer 1

把你的规则分成两部分。索引i是有效的当且仅当它满足以下两种情况：

M[i, j] = 0 for all j != i

• Column

• 行条件：条件：M[k, i] = 1 for all k != i

这使我们注意到，索引i的条件为真等于i'th行为全为零，而i'th列为所有1，但在M[i, i]处相交的情况除外，后者可以具有任何值。

对于具有i=3有效(且无编号的条目不相关)的说明：

. . . 1 . .
. . . 1 . .
0 0 0 x 0 0
. . . 1 . .
. . . 1 . .
. . . 1 . .

现在，考虑使用i, j和i != j的任何对。

如果condition.

• If
• ，我们知道i不是一个有效的索引，因为它失败了行
• M[i, j] = 0，我们知道j不是有效的索引，因为它失败了列条件。

因此，对于矩阵元素M[i, j]的每一个查询，我们都可以从考虑中删除一个索引。这也意味着最多只有一个索引是有效的。否则，如果i1和i2都是有效的，我们就会有一个矛盾，根据上面的规则测试M[i1, i2]。

下面是整个算法在长度为3的矩阵上的一个例子，竞赛树结构只取决于叶节点的数目，稍后将详细介绍。

0 0 1
1 0 1
0 1 1

​

​

在这里，第一个匹配(即同级叶节点)是(0, 1)。查询M[0, 1]返回0，因此消除了第二个索引1。我们删除leafs的父节点，并将其替换为其余索引的0节点。然后将(0, 2)作为新的同胞叶节点进行匹配。查询M[0, 2]返回1，因此消除了第一个索引0。2是剩下的唯一可能有效的索引。

现在，要测试2是否有效，我们需要知道M[2, 0], M[2, 1], M[0, 2], M[1, 2]的值。我们已经查询了M[0, 2]的值，所以我们不会重复这个查询。这为我们提供了2 + 3 = 5总查询，完全满足您的3*n - 3 - floor(log_2(n)) = 9 - 3 - 1 = 5范围。

一旦我们有了最多一个潜在的有效索引，我们就需要对其列和行的2n - 2查询来测试这两种情况。目前，这为我们提供了n-1查询，以消除除一个索引之外的所有索引，然后为测试该索引的2n-2查询，总共提供了太多的3n-3查询。

但是，我们可以使用初始的“消除”查询来计算后面的“测试”查询。创建一个完整的二叉树，其中叶节点是索引0, 1, ... n-1。使用此树作为竞赛树来确定初始消除查询:每个叶节点与其同级叶节点反复配对，直到一个节点保留。

对于n叶节点，在任何完整的二叉树中，叶节点的最小深度(也就是索引参与的匹配/消除查询的最小数目)总是floor(lg_2(n))。因此，我们必须进行的查询的总数最多是

(n-1) + (2n-2) - floor(lg_2(n))，这就是(3n-3) - floor(lg_2(n))。

下面是该算法的Python实现，它应该与命令式伪代码相距不远。它特别冗长，并且被分解成小函数，所以对M的所有访问都是通过一个特殊的query函数完成并记录下来的。这将使您更清楚地知道，实际满足了对全部查询的限制。

def find_valid_index(matrix: List[List[int]]) -> Optional[int]:
    """Given square binary matrix, return the index i
    such that, for all j != i,
    matrix[i, j] = 0 and matrix[j, i] = 1, or None if none exist."""

    num_rows = len(matrix)
    assert num_rows == len(matrix[0])

    if num_rows == 1:
        return 0

    fulfilled_queries = {}

    def query(i: int, j: int) -> int:
        if (i, j) not in fulfilled_queries:
            fulfilled_queries[i, j] = matrix[i][j]

        return fulfilled_queries[i, j]

    def index_to_eliminate(i: int, j: int) -> int:
        assert i != j

        return j if query(i, j) == 0 else i

    def is_valid_index(i: int) -> bool:
        """Test full row and column for validity"""
        for j in range(num_rows):
            if j == i:
                continue
            if query(i, j) == 1 or query(j, i) == 0:
                return False
        return True

    candidate_indices = list(range(num_rows))

    # Find distance from nearest power of two at most num_rows
    leftover_leafs = num_rows - 2**(math.floor(math.log2(num_rows)))

    if leftover_leafs > 0:
        eliminated_indices = set()
        for k in range(leftover_leafs):
            index1 = candidate_indices[2*k]
            index2 = candidate_indices[2*k+1]
            eliminated_indices.add(index_to_eliminate(index1, index2))

        candidate_indices = [x for x in candidate_indices
                             if x not in eliminated_indices]

    while len(candidate_indices) > 1:
        assert len(candidate_indices) % 2 == 0

        eliminated_indices = set()
        for k in range(0, len(candidate_indices), 2):
            index1 = candidate_indices[k]
            index2 = candidate_indices[k + 1]
            eliminated_indices.add(index_to_eliminate(index1, index2))

        candidate_indices = [x for x in candidate_indices
                             if x not in eliminated_indices]

    if len(candidate_indices) == 0:
        return None

    if is_valid_index(candidate_indices[0]):
        return candidate_indices[0]

    return None