algorithm - 如何使用共享元素对列表进行聚类
问题描述
这是我目前在 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]]
非常感谢。
解决方案
如下从列表中准备一个图形,并使用深度优先搜索找到连接的组件。
每个列表都会产生将第一个元素与其他元素连接起来的无向边,例如,
[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
推荐阅读
- angular - 在提交时验证子组件
- reactjs - 如果从反应应用程序发出多个请求,Django(不是休息框架)不记得会话
- php - windows 2016,php dns 查询失败,除非首先以管理员身份运行
- javascript - 仅显示日期字符串中的日期和月份
- python - 中间输出应该在 [-1, 1] 但 tanh 激活饱和 - 解决方案?
- opencv - Darknet.exe 在运行时打印出 Cuda 和 Opencv 版本
- css - Bootstrap v5 中固定列的问题
- c# - WPF InputSimulator 不适用于用户控件
- java-8 - Java 8 - SQL 时间戳到即时格式正确的时间
- api - 没有“假期回复”的Gmail中的自动回复?