Codewars实现array_diff函数报list.remove(x)不存在错误求助

题目要求 #

实现差集函数，完成两个列表的相减操作，规则如下：

• 移除列表a中所有存在于列表b内的值
• 保留剩余元素的原有顺序
• 若某值存在于列表b中，必须将其在列表a中的所有匹配项全部移除

题目给出的参考示例：

array_diff([1,2],[1]) == [2]
array_diff([1,2,2,2,3],[2]) == [1,3]

原有代码的错误原因 #

第一版while循环版本 #

def array_diff(a, b):
    result = a
    for i in a:
        while i in b:
            result.remove(i)
    return result

触发ValueError: list.remove(x): x not in list的核心原因有两个：

1. result = a没有创建新列表，只是给原列表a加了一个别名，遍历原列表的同时动态删除列表元素，会导致遍历索引和实际元素位置错位
2. while循环逻辑存在缺陷：只要当前遍历的元素i在b中，就会反复执行删除操作，当该元素已经被之前的删除操作从列表中移除后，再调用remove(i)就会找不到目标值抛出异常。

第二版if替换while的版本 #

把while换成if后依然无法通过全部测试用例，比如输入a=[1,2,2]、b=[2]时返回[1,2]和预期不符，本质原因还是遍历列表的同时修改列表本身导致索引错位：

• 初始列表是[1,2,2]，遍历到索引0时元素是1，不在b中，不做操作
• 遍历到索引1时元素是2，在b中，执行删除操作，此时列表变为[1,2]，原本在索引2位置的第二个2前移到索引1位置
• 下一轮遍历直接走到索引2位置，但此时列表长度只有2，没有索引2对应的元素，遍历提前结束，剩下的2没有被删除。

正确实现方案 #

不要在遍历原列表的时候直接做删除操作，最稳妥的方式是遍历原列表，把符合要求（不在b中）的元素添加到新列表里，从根源上避免索引错位问题。

高效版本（推荐） #

先把列表b转为集合，把元素查找的时间复杂度从O(n)降到O(1)，再用列表推导式生成结果：

def array_diff(a, b):
    exclude = set(b)
    return [x for x in a if x not in exclude]

这个写法完全符合题目要求：不会修改原列表、保留元素原有顺序、会过滤掉所有出现在b中的元素，大输入场景下性能也足够好。

直白易读版本 #

如果对集合不熟悉，也可以用普通循环逐元素判断追加的写法，逻辑完全一致：

def array_diff(a, b):
    res = []
    for num in a:
        if num not in b:
            res.append(num)
    return res

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