问个技术问题:
比如: [("a", "b"), ("b", "c"), ("e", "f")]
合并成
[set("a", "b", "c"), set("e, "f")]
(即与有一个元素有交集的,就合并进来)
============= 原列表中有一千个元组,半天没出结果
我写的代码:
# l = [("a", "b"), ("b", "c"), ("e", "f")]
def merger(l):
out_list = []
for item in l:
temp_set = set(item)
if len(out_list) == 0:
out_list.append(temp_set)
else:
for item_set in out_list:
if len(temp_set & item_set) > 0:
item_set.update(temp_set)
else:
out_list.append(temp_set)
1
doraemon1293 2018-12-12 18:17:10 +08:00
set(itertools.chain(*arr))
|
2
doraemon1293 2018-12-12 18:18:25 +08:00
没仔细看题,,,,忽略我写的吧..
|
3
sikariba 2018-12-12 18:23:17 +08:00
不确定你程序半天没出结果的原因,但是你的 inner loop 里面不应该再从头遍历 out_list 了,因为前面的元素已经遍历过了,你把 l 里的元素换个顺序,改成[ ("e", "f"), ("a", "b"), ("b", "c")]再运行试试,肯定有重复的
|
4
doraemon1293 2018-12-12 18:24:19 +08:00
union find
``` from collections import defaultdict class DSU: def __init__(self): self.weights = {} self.parents = {} def find(self, x): if x not in self.parents: self.parents[x] = x self.weights[x] = 1 return x else: path = [x] while self.parents[path[-1]] != path[-1]: path.append(self.parents[path[-1]]) root = path[-1] for node in path: self.parents[node] = root return root def union(self, elements): roots = [self.find(e) for e in elements] heaviest_root = max([(self.weights[root], root) for root in roots])[1] for root in roots: if root != heaviest_root: self.weights[heaviest_root] += self.weights[root] self.parents[root] = heaviest_root def merger(A): """ :type A: List[int] :rtype: int """ dsu = DSU() for a in A: dsu.union(a) d=defaultdict(set) for k,x in dsu.parents.items(): d[x].add(k) return list(d.values()) ``` |
5
Jex 2018-12-12 18:29:29 +08:00 1
如果是 [("a", "b"), ("b", "c"), ("c", "d")] 呢?全合并成一个?
|
6
mmixxia 2018-12-12 18:30:12 +08:00
建立一个无向图,然后输出 里面所有没有连接在一起的子图就可以了,非常简单的。
|
7
sikariba 2018-12-12 18:38:54 +08:00
你程序死循环的原因应该是这里
``` for item_set in out_list: if len(temp_set & item_set) > 0: item_set.update(temp_set) else: out_list.append(temp_set) ``` 你不断迭代 out_list,然后又不断对它 append,就永远都遍历不完。常见错误了。 |
8
rabbbit 2018-12-12 19:04:02 +08:00
|
9
ihciah 2018-12-12 19:11:02 +08:00 1
这不是并查集嘛
|
10
aijam 2018-12-12 19:27:00 +08:00
|
11
mskf 2018-12-12 20:44:41 +08:00
并查集。。。
|
12
hustlibraco 2018-12-12 22:42:46 +08:00
# coding=utf-8
# input = [('a', 'b'), ('b', 'c'), ('e', 'f')] # output = [{'a', 'b', 'c'}, {'e', 'f'}] def union_set(items): ret = [] mark = {} for item in items: for n in item: if n in mark: for m in item: ret[mark[n]].add(m) mark[m] = mark[n] break else: index = len(ret) s = set() for n in item: s.add(n) mark[n] = index ret.append(s) return ret if __name__ == "__main__": inputs = [('a', 'b'), ('b', 'c'), ('a', 'e', 'f')] print(union_set(inputs)) |