java - 更新 map 中的值

Question

我正在尝试更新具有多对一关系的 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));

Answer 1

使用联合查找数据结构来解决您的问题。

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