<p>如果您同意将输出的结构从名称更改为爱好集,则可以在线性时间内完成(忽略边缘情况,即大量哈希冲突):</p>
<pre><code>from collections import defaultdict
data = [
{'name': 'John', 'hobbies': ['Reading', 'Swimming']},
{'name': 'Gina', 'hobbies': ['Skating', 'Cooking']},
{'name': 'John', 'hobbies': ['Gardening', 'Swimming']}
]
output = defaultdict(set)
for d in data:
output[d['name']].update(d['hobbies'])
print(output)
# defaultdict(<class 'set'>, {'John': {'Reading', 'Swimming', 'Gardening'},
# 'Gina': {'Cooking', 'Skating'}})
</code></pre>
<p>如果您坚持使用dict列表,您仍然可以实现几乎线性时间(列表查找仍然是O(n)),但是使用一个逻辑将索引映射到名称:</p>
<pre><code>data = [
{'name': 'John', 'hobbies': ['Reading', 'Swimming']},
{'name': 'Gina', 'hobbies': ['Skating', 'Cooking']},
{'name': 'John', 'hobbies': ['Gardening', 'Swimming']}
]
output = []
names_to_indices = {}
for d in data:
if d['name'] not in names_to_indices:
output.append({'name': d['name'], 'hobbies': d['hobbies']})
names_to_indices[d['name']] = len(output) - 1
else:
index = names_to_indices[d['name']]
for hobbie in d['hobbies']:
if hobbie not in output[index]['hobbies']:
output[index]['hobbies'].append(hobbie)
print(output)
# [{'name': 'John', 'hobbies': ['Reading', 'Swimming', 'Gardening']},
# {'name': 'Gina', 'hobbies': ['Skating', 'Cooking']}]
</code></pre>
<p>如果您同意业余爱好是一个集合,那么您可以将其设为真正的线性时间(同样,如果我们忽略了过度哈希冲突的可能性):</p>
<pre><code>data = [
{'name': 'John', 'hobbies': ['Reading', 'Swimming']},
{'name': 'Gina', 'hobbies': ['Skating', 'Cooking']},
{'name': 'John', 'hobbies': ['Gardening', 'Swimming']}
]
output = []
names_to_indices = {}
for d in data:
if d['name'] not in names_to_indices:
output.append({'name': d['name'], 'hobbies': set(d['hobbies'])})
names_to_indices[d['name']] = len(output) - 1
else:
index = names_to_indices[d['name']]
output[index]['hobbies'].update(d['hobbies'])
print(output)
# [{'name': 'John', 'hobbies': {'Gardening', 'Swimming', 'Reading'}},
# {'name': 'Gina', 'hobbies': {'Skating', 'Cooking'}}]
</code></pre>