如何在线性时间内找出矩阵中第i行全0且第i列全1的索引i

复杂度判定结论 #

你当前实现的代码不属于线性时间复杂度，实际时间复杂度为O(N²)，推导逻辑如下：

• 外层循环遍历所有N个可能的索引，共执行N次
• 每次循环内调用2次binaryToDecimal函数，已知该函数单次运行耗时为O(N)
• 总时间开销为 N * 2 * O(N) = O(N²)，属于平方级复杂度，不符合题目要求。

正确的线性时间实现方案 #

该问题存在一个核心特性：符合要求的索引最多仅存在1个。假设存在两个符合条件的索引i和j，那么第i行要求X[i][j] = 0，而第j列要求X[i][j] = 1，二者矛盾，因此最多仅存在1个解。基于这个特性可以实现O(N)时间复杂度的解法：

1. 第一轮遍历：筛选候选索引（O(N)时间）
   初始化候选索引为0，依次遍历后续所有索引：

• 若X[candidate][i] == 1：说明当前候选的行不可能全为0，将候选更新为i
• 若X[candidate][i] == 0：说明第i列不可能全为1，i不可能是解，保留原候选

2. 第二轮遍历：验证候选索引（O(N)时间）
   分别检查候选索引对应的行、列是否符合要求（交点元素不做校验），符合则返回候选值，否则返回-1。

总时间复杂度为O(N)，仅需要两轮线性遍历，不需要额外的数值转换开销，示例实现如下：

def zero_one(X):
    N = len(X)
    # 筛选候选
    candidate = 0
    for i in range(1, N):
        if X[candidate][i] == 1:
            candidate = i
    # 校验行：除交点外全为0
    for j in range(N):
        if j != candidate and X[candidate][j] != 0:
            return -1
    # 校验列：除交点外全为1
    for j in range(N):
        if j != candidate and X[j][candidate] != 1:
            return -1
    return candidate

内容的提问来源于stack exchange，提问作者Dina