如何高效查找矩阵中各列值均严格小于其他行的行？

我们需要在给定矩阵中查找是否存在这样的行——该行的每一列元素都严格小于其他所有行对应列的元素。如果存在，返回该行的索引；不存在则返回无符合条件行的结果。

示例 #

矩阵A #

A = [[7,5,8,2],
     [10,3,7,8],
     [6,2,6,1]]

矩阵A中，索引为2的行[6,2,6,1]满足条件：它的每个元素都严格小于另外两行对应列的元素，因此返回索引2。

矩阵B #

B = [[7,5,8,2],
     [10,3,7,8],
     [9,5,6,7],
     [6,2,6,1]]

矩阵B中不存在满足条件的行：比如索引3的行第3列元素是6，而索引2的行对应列元素也是6，不满足严格小于的要求。

更简洁的实现方式 #

除了逐列循环和其他所有行逐一比较的常规写法，我们可以利用列的第二小值特性来简化逻辑，优化效率：

核心思路 #

如果某一行的所有元素都严格小于对应列的第二小值，那么该行必然严格小于其他所有行的对应列元素——因为第二小值是除了最小值外的次小值，只要比第二小值小，就意味着是该列的唯一最小值，且小于所有其他元素。

Python实现（两种方式） #

1. 利用NumPy简化矩阵运算

import numpy as np

def find_target_row(matrix):
    arr = np.array(matrix)
    row_count = arr.shape[0]
    if row_count <= 1:
        return 0 if row_count == 1 else None
    
    # 对每一列排序，取第二小的元素
    sorted_columns = np.sort(arr, axis=0)
    second_min_per_col = sorted_columns[1]
    
    # 遍历每行检查是否满足条件
    for idx, row in enumerate(arr):
        if np.all(row < second_min_per_col):
            return idx
    return None

# 测试示例
print(find_target_row(A))  # 输出: 2
print(find_target_row(B))  # 输出: None

2. 纯Python实现（无第三方依赖）

def find_target_row(matrix):
    row_count = len(matrix)
    if row_count <= 1:
        return 0 if row_count == 1 else None
    
    # 计算每一列的第二小值
    second_min_cols = []
    # 转置矩阵获取每一列
    for col in zip(*matrix):
        sorted_col = sorted(col)
        second_min_cols.append(sorted_col[1])
    
    # 检查每行是否所有元素都小于对应列的第二小值
    for idx, row in enumerate(matrix):
        if all(num < sec_min for num, sec_min in zip(row, second_min_cols)):
            return idx
    return None

# 测试示例
print(find_target_row(A))  # 输出: 2
print(find_target_row(B))  # 输出: None

效率对比 #

常规逐行逐列比较的时间复杂度是O(n²m)（n为行数，m为列数），而这种基于第二小值的方法时间复杂度为O(nm log n)，在行数较多时效率提升明显，代码逻辑也更简洁直观。

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