python - 返回列表中重复元素并在列表中查找缺失元素的最快方法？

Question

所以我的代码如下图所示。输入是一个只有一个重复项和一个缺失项的列表。答案是一个包含两个元素 long 的列表，第一个是列表中的重复元素，第二个是列表中缺失的元素，范围为 1 到 n。示例 =[1,4,2,5,1] 答案=[1,3]下面的代码有效。

我错了，复杂度是 O(n)，在 Python 中有没有更快的方法来实现这个？另外，有什么办法可以在不使用额外空间的情况下做到这一点。

注意:元素的数量级可能是 10^5 或更大

    n = max(A)
    answer = []
    seen = set()
    for i in A:
        if i in seen:
            answer.append(i)
        else:
            seen.add(i)

    for i in xrange(1,n):
        if i not in A:
            answer.append(i)
    print ans

Answer 1

你确实是正确的，这个算法的复杂度是 O(n)，这是你能达到的最好结果。您可以尝试通过在完成重复值后立即中止搜索来优化它。但最坏的情况是您的副本位于列表的最后面，您仍然需要完全遍历它。

使用散列(你使用一个集合)是一个很好的解决方案。还有很多其他方法，例如使用 Counters。但这不会改变算法的渐近复杂度。

正如@Emisor 建议的那样，您可以利用您拥有一个包含 1 个重复值和 1 个缺失值的列表的信息。正如您可能知道的那样，如果您有一个没有重复值和缺失值的列表，则将列表的所有元素相加会得到 1+2+3+..+n，它可以被重写在数学等价物中 (n*n+1)/2

当您发现重复值时，您可以计算缺失值，而无需执行:

for i in xrange(1,n):
    if i not in A:
        answer.append(i)

既然您知道所有值都存在时的总和:total = (n*n+1)/2) = 15，并且您知道哪个值是重复的。通过获取数组 A = [1,4,2,5,1] 的总和，即 13 并删除重复值 1 , 结果为 12。

将计算出的总数减去计算出的 12 得到 3。

这一切都可以写在一行中:

(((len(A)+1)*(len(A)+2))/2)-sum(A)-duplicate