数据结构和算法-10-删除序列中重复的元素并保持顺序不变

问题描述

怎样在一个序列中删除重复的元素并保持元素顺序不变?

解决方案

如果序列上的值都是 hashable 类型,那么可以很简单的利用集合或者生成器来解决这个问题。

比如:

1
2
3
4
5
6
def dedupe(items):
seen = set()
for item in items:
if item not in seen:
yield item
seen.add(item)

下面是使用上述函数的例子:

1
2
3
4
>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]
>>>

这个方法仅仅在序列中元素为 hashable 的时候才管用。

如果我们想消除元素不可哈希的序列(比如 dict类型)中重复元素的话,需要将上述代码稍微改变一下,就像这样:

1
2
3
4
5
6
7
def dedupe(items, key=None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)

这里的 key 参数指定了一个函数,将序列元素转换成 hashable 类型。

下面是它的用法示例:

1
2
3
4
5
6
>>> a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}]
>>> list(dedupe(a, key=lambda d: (d['x'],d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
>>>

如果你想基于单个字段、属性或者某个更大的数据结构来消除重复元素,第二种方案同样可以胜任。

扩展讨论

如果我们仅仅就是想消除重复元素,通常可以简单的构造一个集合

比如:

1
2
3
4
5
>>> a
[1, 5, 2, 1, 9, 1, 5, 10]
>>> set(a)
{1, 2, 10, 5, 9}
>>>

然而,这种方法不能维护元素的顺序生成的结果中的元素位置被打乱,而上面的方法可以避免这种情况。

在本节中我们使用了生成器函数让我们的函数更加通用,不仅仅是局限于列表处理。

比如,如果我们想读取一个文件,消除重复行,可以这样做:

1
2
3
with open(somefile,'r') as f:
for line in dedupe(f):
...

上述 key 函数参数模仿了 sorted() , min()max() 等内置函数的相似功能。

毕小烦 wechat
「请扫一扫上面的二维码,关注老毕的微信公众号」
「您的赞赏是老毕持续创作的动力」