python-3.x - 这两种算法的区别

Question

问题是返回数组中删除的重复数字。 link

这是解决方案。

    dict1={}
    arr=[]
    for i in nums:
        if i not in dict1:
            dict1[i]=1
            arr.append(i)
    nums[:]=arr
    return len(nums)

这是我的方法……为什么不起作用？

    hash = {}
    for num in nums:
        if num in hash:
            nums.remove(num)
        hash[num] = num
    return len(nums)

我已经研究这个问题超过 30 分钟了:(

Answer 1

从算法的角度来看，第二种看起来不太好，因为remove的时间复杂度比哈希插入和删除要高。因此，删除时间超过 O(1)。第一个实现使用一个额外的列表。此外，除了维护另一个数组，您还可以执行 list (hash.keys ()) 并返回它。

对于平均情况和分摊情况，Python 列表删除都是 O(n)(检查 https://wiki.python.org/moin/TimeComplexity ？)，但 dict 操作在平均情况下是 O(1)和 O(n) 摊销时间。在这种情况下，我在字典中标记元素然后返回键是一个更好的主意。

不过，在这种情况下，我认为使用集合 set 来标记唯一项可能是一个更好的主意，因为它不仅速度更快，而且内存更轻。

从代码的角度来看，不要修改您正在迭代的列表，除非您使用索引访问和修改列表并自行处理列表修改和索引操作。