如何高效检查矩阵元素连续性及多条件匹配实现方案

咱们来拆解这个问题，分成两个核心部分解决：如何高效检查单行内两个元素是否连续，以及如何快速遍历矩阵A并匹配矩阵B的行条件。

一、高效检查单行内的连续元素对 #

要判断一行中是否存在某两个元素连续（比如num1紧跟num2），最直接且最优的方式是单次遍历该行——毕竟你必须逐个检查相邻元素对才能确定结果。这里可以写一个简洁的工具函数：

def has_consecutive_pair(arr, target_pair):
    """检查数组arr中是否存在target_pair的连续出现（顺序固定）"""
    for i in range(len(arr) - 1):
        if arr[i] == target_pair[0] and arr[i+1] == target_pair[1]:
            return True
    return False

# 如果允许元素顺序颠倒（比如num2紧跟num1也算满足），可以修改为：
def has_consecutive_pair_bidirectional(arr, target_pair):
    x, y = target_pair
    for i in range(len(arr) - 1):
        if (arr[i] == x and arr[i+1] == y) or (arr[i] == y and arr[i+1] == x):
            return True
    return False

为什么这是高效的？ #

这个方法的时间复杂度是O(k)（k是单行的长度），这已经是理论最优——因为你至少需要遍历一次所有相邻元素对才能确定是否存在目标对，无法再优化到更低的时间复杂度。

二、高效遍历矩阵A并匹配矩阵B的行条件 #

如果直接暴力遍历：对A的每一行，遍历B的每一行，再分别检查两个元素对是否连续，时间复杂度会是O(m * n * k)（m是A的行数，n是B的行数，k是A行的长度），当A、B规模较大时效率很低。我们可以通过预处理来大幅优化：

优化思路： #

1. 对A的每一行，先提取所有连续元素对并存储在集合中（集合的查找时间是O(1)）；
2. 对B的每一行，预先拆分成两个目标元素对；
3. 对A的每一行，只需检查B中是否存在某一行的两个元素对都在该行的连续对集合中。

代码实现 #

def preprocess_b_matrix(B):
    """预处理B矩阵，将每行拆分为两个元素对的元组"""
    return [ ((row[0], row[1]), (row[2], row[3])) for row in B ]

def check_a_row_against_b(a_row, b_pairs_list):
    """检查A的单行是否满足B中某一行的两个连续元素对条件"""
    # 预处理当前A行的所有连续元素对
    a_consecutive_pairs = set( (a_row[i], a_row[i+1]) for i in range(len(a_row)-1) )
    # 遍历B的预处理结果，只要找到符合条件的就返回True
    for pair1, pair2 in b_pairs_list:
        if pair1 in a_consecutive_pairs and pair2 in a_consecutive_pairs:
            return True
    return False

# 主流程
def process_matrices(A, B):
    b_pairs = preprocess_b_matrix(B)
    result = []
    for row in A:
        result.append(check_a_row_against_b(row, b_pairs))
    return result

优化后的时间复杂度 #

• 预处理B矩阵：O(n)（n是B的行数）；
• 处理A的每一行：预处理连续对是O(k)，遍历B的预处理结果是O(n)；
• 总时间复杂度：O(n + m(k + n))*，对比暴力法的O(m*n*k)，当k较大时（比如A的每行有大量数字），效率提升非常明显。

额外优化点 #

• 如果B矩阵中有重复的行，可以先去重：b_pairs = list(set(preprocess_b_matrix(B)))，减少后续遍历次数；
• 如果允许元素对顺序颠倒，预处理A行的连续对时要加入双向对：a_consecutive_pairs = set( (a_row[i], a_row[i+1]) for i in range(len(a_row)-1) ) | set( (a_row[i+1], a_row[i]) for i in range(len(a_row)-1) )，或者在检查时判断目标对或其反向是否在集合中。

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