gpt4 book ai didi

arrays - 获取一组字符串对并返回所有连接项的数组

转载 作者:数据小太阳 更新时间:2023-10-29 07:54:49 24 4
gpt4 key购买 nike

我有一组名称对,例如:

[
['alison', 'jason'],
['alison', 'chris'],
['john', 'bill'],
['bill', 'alex'],
['alex', 'jack']
]

我正在尝试编写一个可以接受它并返回的方法

[
['alison', 'jason', 'chris'],
['john', 'bill', 'alex', 'jack']
]

比 O(N^2) 时间要好。我的尝试是这样的:

def teams(arr)
pair_hash = {}
arr.each do |pair|
if pair_hash[pair[0]].nil?
pair_hash[pair[0]] = [pair[1]]
else
pair_hash[pair[0]].push(pair[1])
end
end
teams = []
pair_hash.map do |leader, team|
teams.push(find_teammates(pair_hash, leader, team))
end
teams
end

def find_teammates(hash, leader, team)
result = [leader]
team.each do |member|
if hash[member].nil?
result += [member]
else
result += find_teammates(hash, member, hash[member])
end
end
result
end

但是这个解决方案在结果中有额外的团队,而且我能想到的每个解决方案都涉及非常差的时间复杂度。如果您知道如何解决这个问题而不只是强行通过所有对,我很想知道。

最佳答案

你很幸运,disjoint-set 是我最喜欢的数据结构。这是一个快速的'n'dirty 实现:

pairs = [['alison', 'jason'], ['alison', 'chris'], ['john', 'bill'], ['bill', 'alex'], ['alex', 'jack'], ['steve', 'alex']]

parents = {}

pairs.each do |x, y|
# each person starts as their own set, and their own representative
parents[x] ||= x
parents[y] ||= y

# find representative of x set
x_parent = parents[x]
loop do
break if parents[x_parent] == x_parent
x_parent = parents[x_parent]
end

# find representative of y set
y_parent = parents[y]
loop do
break if parents[y_parent] == y_parent
y_parent = parents[y_parent]
end

# union by changing y's representative
parents[y_parent] = x_parent
# path compression to speed up later unions
parents[x] = x_parent
parents[y] = x_parent
end

# group by set representative (some paths might not be compressed)
groups = parents.each_key.group_by do |person|
parent = parents[person]
loop do
break if parents[parent] == parent
parent = parents[parent]
end
parent
end

p groups.values
[["alison", "jason", "chris"], ["john", "bill", "alex", "jack", "steve"]]

这大约是 O(N+M),其中 N 是人数,M 是对数。注意重复,例如在查找集合的代表时。如果您定义一个适当的类来执行查找,该算法看起来会更清晰。

我的路径压缩也不理想,如果将压缩放在代表查找而不是联合中,您可以加快速度。

关于arrays - 获取一组字符串对并返回所有连接项的数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50454751/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com