如何对Python列表进行排序和去重？

Question

给定一个字符串列表，我想按字母顺序对其进行排序并去重。我知道可以这样做：

from sets import Set
[...]
myHash = Set(myList)

但是我不知道如何按字母顺序检索哈希表中的列表成员。

我并不执着于使用哈希表，因此任何实现此目标的方法都可以。此外，性能不是问题，因此我更喜欢一个清晰的代码解决方案，而不是一个更快但更不透明的解决方案。

- jmglov

---

此外，更多信息请参见这里。 - user1129682

这个问题经过@ColonelPanic的编辑后变得有点混乱; 标题中的问题和正文中的问题并不相同。标题表明原始顺序，在去除重复项之前，应该被保留。但是正文中提出了一种情况，实际上并不需要这样做。 - Mark Amery

我已经修改了标题以匹配正文和被接受的答案。 - Vladimir Panteleev

Answer 1

可以使用内置函数对列表进行排序和去重：

myList = sorted(set(myList))

• set是Python >= 2.3的内置函数
• sorted是Python >= 2.4的内置函数

- Rod Daunoravicius

---

如果你的myList包含不可哈希的对象，那么这个方法就不能使用。 - J_Zar

@CorneliuZuzu 使用set()删除重复项会改变顺序，因此您必须以这种方式进行操作。 - Dimali

因为有序和排序之间存在区别，所以被踩了。有序意味着保持原始顺序，例如 f([3,1,4,1,5,9,2,6,5,3,5]) = [3,1,4,5,9,2,6]。 - Ken Seehart

@user3667349，“保持顺序”条款不是原始问题的一部分，而是由Colonel Panic在2015年进行的编辑添加的。 - Rod Daunoravicius

@ZuzuCorneliu的set没有保持顺序，因此经过排序后的set会再次使列表无序。 - thinkingmonster

Answer 2

如果你的输入已经排序好了，那么可能有一种更简单的方法：

from operator import itemgetter
from itertools import groupby
unique_list = list(map(itemgetter(0), groupby(yourList)))

- sykora

---

这也可以表示为[e for e，_ in groupby（sortedList）]。 - Rafał Dowgird

这是O(n)而不是O(n log n)，对吗？ - Colonel Panic

值得一提的是，类似的内容已经被添加到了itertools文档中的recipes列表中。 - Cristian Ciupitu

Answer 3

如果你想保留原始列表的顺序，只需要使用带有None值的OrderedDict。

在Python2中：

from collections import OrderedDict
from itertools import izip, repeat

unique_list = list(OrderedDict(izip(my_list, repeat(None))))

在Python3中，这甚至更简单：

from collections import OrderedDict
from itertools import repeat

unique_list = list(OrderedDict(zip(my_list, repeat(None))))

如果你不喜欢迭代器（zip和repeat），你可以使用生成器（在2和3中都适用）：

from collections import OrderedDict
unique_list = list(OrderedDict((element, None) for element in my_list))

- Paweł Sobkowiak

Answer 4

如果你更看重清晰度而不是速度，我认为以下内容非常清晰易懂：

def sortAndUniq(input):
  output = []
  for x in input:
    if x not in output:
      output.append(x)
  output.sort()
  return output

虽然使用了not in对输入列表的每个元素进行重复检查，但时间复杂度仍为O(n^2)。

- unwind

Answer 5

>但是我不知道如何按字母顺序从哈希中检索列表成员。

这并不是你的主要问题，但是为了以后的参考，Rod的答案使用sorted可以用于遍历按排序顺序排列的dict键：

for key in sorted(my_dict.keys()):
   print key, my_dict[key]
   ...

同时由于tuple是按照元组的第一个成员排序的，您也可以使用items来做同样的事情：

for key, val in sorted(my_dict.items()):
    print key, val
    ...

- davidavr

Answer 6

对于字符串数据

output = []

    def uniq(input):
        if input not in output:
           output.append(input)
print output     

- user2515605