在列表中查找项目结尾的重复项。

Question

我希望能够在列表中找到最后3个字符存在重复结尾的项目。

我知道如何使用下面的代码查找重复项，但需要帮助编写代码来查找“sara”和“tamara”的最后一个字符串是否相同，以便将其中一个项目复制到duplicate_finding列表中。

使用以下代码，我只能识别列表中的完全重复项：

names = ["tom", "john", "sara" , "tamara" , "tom"]
single_finds = []
duplicate_finds = []

for i in names:
        if i in single_finds:
                duplicate_finds.append(i)
        else:
                single_finds.append(i)

print (single_finds)
print (duplicate_finds)

输出：

['tom', 'john', 'sara', 'tamara']
['tom']

- sebastian20182018

Answer 1

一种方法是使用 itertools.groupby 并指定我们想基于最后的 n 个字符进行分组，这可以通过使用 key 参数实现。

然后，我们可以使用 itertools.chain 来展开列表并删除那些只有一个元素的子列表，并使用 set 去重（如果你想要它们，则可以使用 list）：

from itertools import groupby, chain
k = lambda x: x[-3:]
l = [list(v) for _,v in groupby(sorted(names, key=k), key=k)]
# [['tamara', 'sara'], ['john'], ['tom', 'tom']]
[i[0] for i in l if len(i) > 1]
# ['tamara', 'tom']

- yatu

---

这只是巧合，因为sara和tamara恰好相邻排列在列表中。你应该按照最后三个字符进行排序。（通常情况下，sorted和groupby的key应该相同。） - tobias_k

哦，你说得对，我也应该使用键进行排序，谢谢@tobias_k。已更新，好发现。 - yatu

你能否更改代码，以便仅打印重复项（仅“sara”或“tamara”），因为我想从原始列表中删除所有重复项？ - sebastian20182018

Answer 2

使用字典逐个后缀累积名称，然后收集结果：

最初的回答：

>>> from collections import defaultdict 
>>> d = defaultdict(list) 
>>> for name in names: 
...     suffix = name[-3:] 
...     d[suffix].append(name) 
... 
>>> for suffix, names in d.items(): 
...     print("-", suffix, ":", *names) 
... 
- tom : tom tom
- ohn : john
- ara : sara tamara

你可以通过查看 d.items() 中的 len(names) 来将其分成单个和重复项。

这是一个 O(n) 的时间复杂度解决方案，而基于 groupby 的方法需要在 O(n log n) 上对数据进行预排序。

"Original Answer" 翻译成 "最初的回答"

- wim

Answer 3

通过从末尾切割字符串，将列表按最后3个字符分组，如果名称组中有多个元素，则为重复项，否则为单个项。

import itertools

names = ["tom", "john", "sara" , "tamara" , "tom"]

def find_duplicates(names):
    for key, group in itertools.groupby(sorted(names), lambda x: x[-3:]):
        grouped_items = list(group)
        if len(grouped_items) > 1:
            yield grouped_items[0]

def find_single(names):
    for key, group in itertools.groupby(sorted(names)):
        if len(list(group)) == 1:
            yield key

single_finds = list(find_single(names))
duplicate_finds = list(find_duplicates(names))

print ("Single finds", single_finds)
print ("Duplicate finds", duplicate_finds)

输出：

Single finds ['john', 'sara', 'tamara']
Duplicate finds ['sara', 'tom']

- Kunal Mukherjee

---

但是重复列表中不应包含 "John" - sebastian20182018

@sebastian20182018 对不起，我的错。 - Kunal Mukherjee

Answer 4

为了完成@wim的线性时间答案：

import collections
res=collections.defaultdict(list)

for name in names: 
    res[name[-3:]].append(name)

singles,dummies= [],[]

for v in res.values():
    singles.extend(v[:1])
    dummies.extend(v[1:])

然后：

singles is ['tom', 'john', 'sara']

dummies is ['tom', 'tamara']   

- B. M.