如何筛选出列表中左侧或右侧元素数量≥3的元素？

问题说明 #

我们需要从列表中筛选出符合以下条件的元素：元素的左侧有至少3个元素，或者右侧有至少3个元素。不符合条件的元素将被移除。

单例示例解释 #

输入列表 [1, 2, 3, 4]，输出结果为 [1, 4]：

• 元素1右侧有3个元素，符合条件，保留
• 元素2左侧仅1个元素、右侧仅2个元素，均不足3个，移除
• 元素3左侧仅2个元素、右侧仅1个元素，均不足3个，移除
• 元素4左侧有3个元素，符合条件，保留

更多测试示例 #

[]  =>  []
[1]  =>  []
[1, 2]  =>  []
[1, 2, 3]  =>  []
[1, 2, 3, 4]  =>  [1, 4]
[1, 2, 3, 4, 5]  =>  [1, 2, 4, 5]
[1, 2, 3, 4, 5, 6]  =>  [1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6, 7]  =>  [1, 2, 3, 4, 5, 6, 7]

优化实现方案 #

原参考代码通过反向遍历并调用pop操作实现，但pop的时间复杂度为O(n)，列表较大时效率偏低。我们可以直接生成新列表，只保留符合条件的元素，效率更优：

def filter_elements(lst):
    n = len(lst)
    return [
        elem for idx, elem in enumerate(lst)
        if idx >= 3 or (n - 1 - idx) >= 3
    ]

# 验证所有测试示例
test_cases = [
    [], [1], [1,2], [1,2,3], [1,2,3,4],
    [1,2,3,4,5], [1,2,3,4,5,6], [1,2,3,4,5,6,7]
]
for case in test_cases:
    print(f"{case}  =>  {filter_elements(case)}")

实现逻辑说明 #

• 先获取列表长度n，避免重复计算
• 用列表推导式遍历元素及其索引idx：
  • idx >= 3：代表当前元素左侧有至少3个元素（索引从0开始，索引为3时左侧正好3个元素）
  • n - 1 - idx >= 3：代表当前元素右侧有至少3个元素（n-1是最后一个元素的索引，减去当前索引即为右侧元素数量）
• 列表推导式直接生成结果列表，时间复杂度为O(n)，空间复杂度为O(k)（k为符合条件的元素数量），比原方案更高效

原参考实现（供对比） #

题目中给出的不够优化的实现方式如下：

L = [1, 2, 3, 4]

N = len(L)
for i in reversed(range(N)):
    left = i
    right = N - 1 - i
    if not (left >= 3 or right >= 3):
        L.pop(i)

print(L)

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