我正在尝试更新具有多对一关系的 Map 中的值。
| Keys | Values |
| 1 | {1, 2} |
| 2 | {1, 2} |
| 3 | {3} |
key 1 和 2 指的是同一组。我想合并键 2 和 3 的集合。这样我得到以下内容:
| Keys | Values |
| 1 | {1, 2, 3} |
| 2 | {1, 2, 3} |
| 3 | {1, 2, 3} |
有没有办法不用 O(n) 就能做到这一点?
我目前拥有的:
// Merge sets for keys i and j
Map[Integer, Set[Integer]] map;
map.get(i).addAll(map.get(j));
for(int key : map.get(j)) map.put(key, map.get(i));
最佳答案
使用联合查找数据结构
来解决您的问题。
It supports two useful operations:
Find: Determine which subset a particular element is in. Find typically returns an item from this set that serves as its "representative"; by comparing the result of two Find operations, one can determine whether two elements are in the same subset.
Union: Join two subsets into a single subset.
Just applying this technique alone yields a worst-case running-time of
O(log n)
per MakeSet, Union, or Find operation.
function MakeSet(x)
x.parent := x
function Find(x)
if x.parent == x
return x
else
return Find(x.parent)
function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)
xRoot.parent := yRoot
关于java - 更新 map 中的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31911893/