0

我对 Python 相当陌生，我有兴趣在列表中列出重复项。我知道如何删除列表中的重复项（set() ）以及如何使用collections.Counter列出列表中的重复项；但是，对于我正在处理的项目，这不是最有效的方法，因为运行时间为n(n-1)/2 --> O(n^2)并且 n 介于 5k 之间-50k+ 字符串值。

所以，我的想法是，由于 python 列表是链接的数据结构，并在创建时分配给内存，所以我从创建列表的一开始就开始计算重复项。

  1. 创建列表，第一个索引值是单词“dog”
  2. 第二个索引值是单词'cat'
  3. 现在，它将检查第二个索引是否等于第一个索引，如果它被附加到另一个名为 Duplicates 的列表中。
  4. 第三个索引值被赋值为'dog'，第三个索引会检查它是否等于'cat'然后'dog'；因为它匹配第一个索引，所以它被附加到 Duplicates。
  5. 第四个索引被指定为“dog”，但它只会检查第三个索引，而不是第二个和第一个，因为现在你可以假设，由于第三个和第二个不是重复的，所以第四个不需要之前检查，并且因为第三个/第一个相等，搜索在第三个索引处停止。

我的项目给了我这些值并将其附加到一个列表中，所以我想实现上述算法，因为我不在乎有多少重复项，我只想知道是否有重复项。

我想不出如何编写代码，但我想出了它的基本结构，但我可能完全不知道（使用随机 numgen 以便于使用）：

for x in xrange(0,10):
    list1.append(x)
    for rev, y in enumerate(reversed(list1)):
        while x is not list1(y):
            cond()
            if ???
4

1 回答 1

5

我真的不认为你会比 a 更好collections.Counter：

c = Counter(mylist)
duplicates = [ x for x,y in c.items() if y > 1 ]

构建计数器应该是O(n)（除非你使用的键对散列特别不利——但根据我的经验，你需要非常努力地做到这一点），然后获取重复列表也会O(n)给你一个总复杂度O(2n) == O(n)（用于典型用途）。

于 2012-11-29T01:32:02.577 回答