Codewars限制元素出现次数题出现list index out of range错误求解

题目要求 #

给定列表lst和数字N，生成新列表保留原序列顺序，且每个元素最多出现N次：

• N=2时输入[1,2,3,1,2,1,2,3]，输出为[1,2,3,1,2,3]
• delete_nth ([1,1,1,1],2) 返回 [1,1]
• delete_nth ([20,37,20,21],1) 返回 [20,37,21]

现有代码及报错 #

原代码 #

def delete_nth(order,max_e):
    o = order[::-1]
    x = 0

    while x != len(o)+1:
        if o.count(o[x]) > max_e:
            o.remove(o[x])
        x += 1
        if x >= len(o):
            return(o[::-1])

    return(o[::-1])

报错信息 #

Traceback (most recent call last):
  File "tests.py", line 30, in <module>
    do_test()
  File "tests.py", line 9, in do_test
    test.assert_equals(delete_nth([], 5), [], "From list [],5 you get")
  File "/workspace/default/solution.py", line 6, in delete_nth
    if o.count(o[x]) > max_e:
IndexError: list index out of range

错误原因 #

1. 核心触发点：Codewars测试用例包含空列表输入场景，当order为空时，o = order[::-1]得到的是空列表，进入循环后直接访问o[0]就会触发索引越界，本地未测试空列表边界场景所以未复现报错。
2. 原有逻辑的额外缺陷：边遍历列表边删除元素时，列表长度会动态变化，原有索引递增逻辑容易出现漏判、越界的问题，且每次调用count方法时间复杂度为O(n)，整体效率很低。

修复方案 #

快速修复原有逻辑（仅解决报错） #

在函数开头增加空列表判断即可覆盖边界场景：

def delete_nth(order,max_e):
    if not order:
        return []
    o = order[::-1]
    x = 0
    while x != len(o)+1:
        if o.count(o[x]) > max_e:
            o.remove(o[x])
        x += 1
        if x >= len(o):
            return(o[::-1])
    return(o[::-1])

优化版实现（更稳定高效） #

采用正向遍历+计数器的方案，避免索引问题，时间复杂度更低：

def delete_nth(order, max_e):
    count = {}
    res = []
    for num in order:
        count[num] = count.get(num, 0) + 1
        if count[num] <= max_e:
            res.append(num)
    return res

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