python - 找到第 i 行和第 i 列，使得行中的所有数字都是零，列中的所有数字都是 1

Question

该问题要求在线性时间内找到第 i 行和第 i 列，使得第 i 行仅包含零，第 i 列仅包含 1(它们的交点无关紧要)。如果满足这个条件的i不存在，就返回-1。这是我能想到的最好的:

def zero_one(X):
    X = numpy.array(X)
    N = len(X)
    for i in range(N):
        original_value = X[i][i]
        X[i][i] = 0
        r = binaryToDecimal(X[i, :])
        X[i][i] = 1
        c = binaryToDecimal(X[:, i])
        if r == 0 and c == 2**(N - 1) - 1:
            X[i][i] = original_value
            return i
        X[i][i] = original_value
    return -1 # in case there's no i that satisfies the condition

假设 binaryToDecimal() 以线性时间运行，并且可以像 NumPy 中那样按列运行，这可能是线性的，但我对此表示怀疑。

Answer 1

我相信使用“锦标赛”策略在 O(n) 中是可行的:首先我们将消除除一个以外的所有候选者，然后我们将检查最后一个候选者是否是有效答案。我会给你一个伪代码答案，因为我不会 python，但它应该很容易实现。

1. 创建一个包含第一个索引的变量“champion”。 (此变量将存储锦标赛的当前获胜索引)。
2. 对于每个其他索引 j，将它们与冠军索引进行匹配:如果 X[cham​​pion][j] 为 0，则冠军保留，否则冠军成为 j(如果 X[i][j] 为 1，则第 i 行包含 1，i 无效，如果为 0，则第 j 列包含 0，且有效。因此，每场比赛都会淘汰一名可能的候选人。)
3. 检查冠军是否满足条件:如果满足则返回冠军，否则返回-1。 (所有其他索引已在 2 期间被删除))

编辑:尝试添加 python 代码。

def zero_one(m):
    n = len(m)
    c = 0
    for j in range(1,n):
        if m[c][j] == 1:
            c = j
    for i in range(0,c-1):
        if m[c][i] == 1 or m[i][c] == 0:
            return -1
    for i in range(c+1,n):
        if m[c][i] == 1 or m[i][c] == 0:
            return -1
    return c

复杂度为 0(n):您首先在锦标赛期间检查矩阵的 (n-1) 个元素，然后检查 2(n-1) 个元素以验证最后一个索引。

如果您有任何问题，请随时提出，我会相应更新。