这是我目前无法在 Leetcode 或 StackOverflow 上找到的问题。假设您有一组数字或引用列表:
[[1,2,3],[3,4,5],[6,7,8],[8,9],[10],[7]]
合并这些列表的最快算法是什么,这样输出将是:
[[1,2,3,4,5],[6,7,8,9],[10]]
非常感谢。
最佳答案
按如下所示从列表中准备图表并找到 connected components使用 depth-first search .
每个列表都会产生连接第一个元素和其他元素的无向边,例如,
[1,2,3] -> [(1,2), (1,3)]
[3,4,5] -> [(3,4), (3,5)]
[6,7,8] -> [(6,7), (6,8)]
[8,9] -> [(8,9)]
[10] -> []
[7] -> []
然后运行深度优先搜索以查找连接的组件。在 Python 中,一切都是这样的。
import collections
def merge(lsts):
neighbors = collections.defaultdict(set)
for lst in lsts:
if not lst:
continue
for x in lst:
neighbors[x].add(lst[0])
neighbors[lst[0]].add(x)
visited = set()
for v in neighbors:
if v in visited:
continue
stack = [v]
component = []
while stack:
w = stack.pop()
if w in visited:
continue
visited.add(w)
component.append(w)
stack.extend(neighbors[w])
yield component
关于algorithm - 如何使用共享元素对列表进行聚类,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52213815/