我需要一种有效的方法来合并节点列表(整数对)。
只有当对中有一个公共(public)数字并且公共(public)数字在第一个或最后一个位置时才应该发生合并(否则它已经连接)。
例如:
mylist = [[4, 3], [6, 3]]
merge_links(mylist) # should output [4, 3, 6]
另一个例子:
mylist = [[4, 3], [6, 3], [6, 4]]
merge_links(mylist)
# should output again [4, 3, 6] because both 6 and 4 allready exist in array.
还有一个例子:
mylist = [[4, 3], [6, 3], [6, 4], [6, 2], [7, 4], [4, 9]]
merge_links(mylist)
# should output [7, 4, 3, 6, 2]
# [4, 3] ✔
# [4, 3] + [6, 3] ✔ -> [4, 3, 6]
# [4, 3, 6] + [6, 3] ✘ both 6 and 3 exist in [4, 3, 6]
# [4, 3, 6] + [6, 4] ✘ both 6 and 4 exist in [4, 3, 6]
# [4, 3, 6] + [6, 2] ✔ -> [4, 3, 6, 2]
# [4, 3, 6, 2] + [7, 4] ✔ -> [7, 4, 3, 6, 2]
# [7, 4, 3, 6, 2] + [4, 9] ✘ 4 is allready connected "7-4-3"!
目前我正在使用:
def merge_links(a, b):
inter = np.intersect1d(a, b, True)
a = set(a) - set(inter)
b = set(b) - set(inter)
n = np.unique(list(a) + list(inter) + list(b))
return n
但是对于上面的限制效果不是很好
最佳答案
下面的代码工作如下:
- 创建一个新列表,其大小为旧列表的大小 + 1(最大大小 产量可达)。
- 从你的对列表中的第一对开始,它的第一个值 在你的新列表的末尾,它的第二个值在 你的新 list 。并使用 python 字典将它们标记为已访问 例如。
- 维护指向第一个和最后一个位置的两个索引 最初分别是新列表的结尾和开头。
- 迭代其余的对,如果对 i 它的两个值都存在,或者 字典里没有,略过。否则,合并未访问的 第一个索引或最后一个索引处元素的值(取决于 访问值的位置),并更新您的索引。注意 如果访问值不在第一个或 最后一个索引(如果它在中间某处)。
- 返回新列表[第一个索引结束]与新的串联 列表[从最后一个索引开始]。
注意:每个合并操作都需要 O(1)。如果您知道对值的范围,也可以使用 bool 数组而不是字典。
#The function takes a list of pairs as an argument
def merge_lst(lst):
#Dictionary to check if value is already in array
visited = dict()
#Length of old list
lst_len = len(lst)
#New list will have at most lst_len+1 elements
new_lst = [0]*(lst_len+1)
#Put the first pair values in last and first elements of the new list repectively and mark them as visited
new_lst[lst_len], new_lst[0] = lst[0][0], lst[0][1]
visited[lst[0][0]], visited[lst[0][1]] = True, True
#Maintain the positions of your first and last elements, which are the the last index and 0 respectively now
first_index, last_index = lst_len, 0
#Iterate on the rest of pairs
for i in range(1, lst_len):
#Check if pair[a, b] are already visited
a_exists, b_exists = lst[i][0] in visited, lst[i][1] in visited
#Skip if they both exist or don't exist
if(a_exists == b_exists):
continue
#Assume a was the common one
common, to_merge = lst[i][0], lst[i][1]
#If b exists (b is the common not a), then just swap
if(b_exists):
common, to_merge = lst[i][1], lst[i][0]
#If the common element is at the first index, the first element and index are updated
if(new_lst[first_index] == common):
first_index-=1
new_lst[first_index] = to_merge
visited[to_merge] = True
#If the common element is at the last index, the last element and index are updated
elif(new_lst[last_index] == common):
last_index+=1
new_lst[last_index] = to_merge
visited[to_merge] = True
#Else, the common element is somewhre in the middle (already connected)
#Return concatenation of new_lst[first_index to the end] with new_lst[0 to the last_index]
return new_lst[first_index:lst_len+1]+new_lst[0:last_index+1]
此代码为您提到的所有测试用例提供了正确的输出。
关于python - 合并具有限制的公共(public)整数对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52063999/