更新地图中的值

Question

我正在尝试更新具有多对一关系的地图中的值。

| Keys | Values |
| 1    | {1, 2} |
| 2    | {1, 2} |
| 3    | {3}    |

键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));

Answer 1

用一个 union–find data structure来解决你的问题。

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

Disjoint-set data structure, UnionFind Algorithms

的详细信息

Answer 2

你就快完成了：因为键 1 和 2 已经引用了同一个集合，你只需要从键 3 添加集合的元素，然后让键 3 引用你的合并结果。

// Merge sets for keys i and j
Map[Integer, Set[Integer]] map;
map.get(i).addAll(map.get(j));
map.put(j, map.get(i));

除非我在你的问题中遗漏了一个微妙之处？

编辑：我错过了一个微妙之处：这仅在向集合中添加单个元素时有效。如果 map.get(j) 有一个以上的元素，我看不出有什么办法可以逃避你在问题中建议的循环。

更新地图中的值

Update Value in a Map

java

int

dictionary

hashmap

set