在 3n − 的二进制矩阵中查找所需的索引⌊lg n⌋ − 3

Question

给定一个 n×n 矩阵 M，其中每个条目都是 0 或 1。提出一种算法，确定是否 ∃i, 1 ≤ i ≤ n，使得 M[i,j] = 0 且 M[j,i] = 1, ∀j, 1 ≤j≤ n ∧ j!=i，以检查M的条目作为关键操作。你的算法最多必须检查 3n − ⌊lg n⌋ − 3 M 项。

提示：将“检查 M[i, j]”与比较 i 和 j 联系起来。最初，每个索引都可能是所需的索引 i。将潜在索引 i 的数量从 n 消除到 1。然后验证该索引是否确实是所需的索引 i。

有聪明人可以遮挡更多灯光或提示来解决这个问题吗？我是这个领域的新手，想到的任何方法都以 O(n^2) 结束。有什么建议吗？

我考虑过寻找任何模式的基本情况：

• 2×2 矩阵 M，将每个条目视为比较，然后我们有 4-2(diagonal elts) = 2 比较。如果我们验证所需的运行时间 T(n)，我们有 3n - Floor(lgn)-3 = 3*2 - lg2 -3 = 6-4 = 2comparisons
• 3 -by 3 M, 9 (entries) - 3 (diagonal etls) ) = 6 次比较 所需的 T(n) = 3*3 - Floor(lg3) -3 = 9-4=5
• 4×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 当且仅当满足以下两个条件时才有效：

1. 行条件：M[i, j] = 0 for all j != i
2. 列条件：M[k, i] = 1 for all k != i

这让我们注意到索引 i 的条件为 true 相当于拥有 i'th< /code> 行全为零，并且具有第 i 列全部为 1，除了它们在 M[i, i] 处相交的地方，它可以具有任何值。

对于 i=3 有效的说明（非编号条目不相关）：

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

现在，考虑任何 i, j 与 i != j.

• 如果M[i, j] = 1，我们知道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 被消除。我们删除叶子的父节点，并将其替换为剩余索引的节点 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< /code> 太多了。

但是，我们可以使用初始的“消除”查询来对后面的“测试”查询进行计数。创建一棵完整的二叉树，其中叶节点的索引为 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