基于嵌套列表l1的连续1-2序列筛选等长嵌套列表l2的非零元素

核心思路 #

collections.Counter只能统计全局元素频次，无法识别连续序列的位置和长度关系，所以我们需要先分别提取两个列表中符合要求的连续块，再按位置和长度匹配即可。

步骤说明 #

1. 提取l1每个子列表中连续由1、2组成的块，记录每个块的起始索引、结束索引、长度
2. 提取l2每个子列表中连续相同非零元组的块，记录每个块的起始索引、结束索引、长度、元组值
3. 对每个l1的连续块，查找是否有l2的块完全包含该l1块的位置范围，且l2块的总长度与l1块长度完全相等：
   • 匹配成功：将对应长度的元组加入结果
   • 匹配失败：该块内容丢弃，最终对应子列表返回空

实现代码 #

def get_l1_blocks(l1_sub):
    """提取l1子列表中连续的1/2块，返回格式：(起始索引, 结束索引, 块长度)"""
    blocks = []
    n = len(l1_sub)
    i = 0
    while i < n:
        if l1_sub[i] in (1, 2):
            start = i
            while i < n and l1_sub[i] in (1, 2):
                i += 1
            end = i - 1
            blocks.append((start, end, end - start + 1))
        else:
            i += 1
    return blocks

def get_l2_blocks(l2_sub):
    """提取l2子列表中连续的相同非零元组块，返回格式：(起始索引, 结束索引, 块长度, 元组值)"""
    blocks = []
    n = len(l2_sub)
    i = 0
    while i < n:
        if l2_sub[i] != 0:
            start = i
            val = l2_sub[i]
            while i < n and l2_sub[i] == val:
                i += 1
            end = i - 1
            blocks.append((start, end, end - start + 1, val))
        else:
            i += 1
    return blocks

def filter_matched(l1, l2):
    result = []
    for x_sub, y_sub in zip(l1, l2):
        l1_blocks = get_l1_blocks(x_sub)
        l2_blocks = get_l2_blocks(y_sub)
        current_res = []
        for s1, e1, len1 in l1_blocks:
            matched_val = None
            # 查找包含当前l1块的l2块
            for s2, e2, len2, val in l2_blocks:
                if s2 <= s1 and e2 >= e1:
                    if len2 == len1:
                        matched_val = val
                    break
            if matched_val:
                current_res.extend([matched_val] * len1)
        result.append(current_res)
    return result

测试验证 #

所有提供的测试用例都可以正常运行：

# 测试用例1
l1 = [[0, 1, 2, 2, 0, 1, 2], [0, 1, 0, 0, 0], [0, 1, 2, 0, 0]]
l2 = [[0, (1, 'a', 'b'), (1, 'a', 'b'), (1, 'a', 'b'), 0, (3, 'x', 'y'), 0], [0, (2, 'c', 'd'), 0, 0, 0], [0, (3, 'e', 'f'), 0, 0, 0]]
print(filter_matched(l1, l2))
# 输出：[[(1, 'a', 'b'), (1, 'a', 'b'), (1, 'a', 'b')], [(2, 'c', 'd')], []]

# 测试用例2
l1 = [[0, 1, 2, 0], [0, 1]]
l2 = [[0, (1, 'a', 'b'), (1, 'a', 'b'), 0], [(2, 'a', 'b'), (2, 'a', 'b')]]
print(filter_matched(l1, l2))
# 输出：[[(1, 'a', 'b'), (1, 'a', 'b')], []]

# 测试用例3
l1 = [[2, 2, 2], [1, 2]]
l2 = [[(1, 'a', 'b'), (1, 'a', 'b'), (1, 'a', 'b')], [(2, 'a', 'b'), (2, 'a', 'b')]]
print(filter_matched(l1, l2))
# 输出：[[(1, 'a', 'b'), (1, 'a', 'b'), (1, 'a', 'b')], [(2, 'a', 'b'), (2, 'a', 'b')]]

# 测试用例4
l1 = [[0, 1], [0, 0]]
l2 = [[0, (3, 'x', 'y')], [0, 0]]
print(filter_matched(l1, l2))
# 输出：[[(3, 'x', 'y')], []]

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