1202. 交换字符串中的元素

给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs[i] = [a, b] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

并查集（版本一）

import java.util.*;

class Solution {
    public String smallestStringWithSwaps(String s, List> pairs) {
        UnionSet unionSet = new UnionSet(s.length());

        for (List pair : pairs) {
            unionSet.merge(pair.get(0), pair.get(1));
        }

        Map> membersMap = unionSet.getMembersMap();

        char[] ans = s.toCharArray();

        for (Map.Entry> entry : membersMap.entrySet()) {
            Set members = entry.getValue();
            List raw = new ArrayList<>(members);
            Collections.sort(raw);
            List sorted = new ArrayList<>(members);
            Collections.sort(sorted, new Comparator() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Character.compare(s.charAt(o1), s.charAt(o2));
                }
            });
            for (int i = 0; i < raw.size(); ++i) {
                ans[raw.get(i)] = s.charAt(sorted.get(i));
            }
        }
        return new String(ans);
    }
}

class UnionSet {
    private int[] parent;

    private Map> membersMap;

    public UnionSet(int n) {
        this.parent = new int[n];
        this.membersMap = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
            Set set = new HashSet<>();
            set.add(i);
            membersMap.put(i, set);
        }
    }

    public Map> getMembersMap() {
        return this.membersMap;
    }

    public int find(int x) {
        int f = parent[x];
        if (f == x) {
            return f;
        }
        return find(f);
    }

    public void merge(int a, int b) {
        int f1 = find(a);
        int f2 = find(b);
        if (f1 == f2) {
            return;
        }
        Set m1 = membersMap.get(f1);
        Set m2 = membersMap.get(f2);
        if (m1.size() > m2.size()) {
            parent[f2] = f1;
            m1.addAll(m2);
            membersMap.remove(f2);
        } else {
            parent[f1] = f2;
            m2.addAll(m1);
            membersMap.remove(f1);
        }
    }
}

并查集（版本二）

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {

    public String smallestStringWithSwaps(String s, List> pairs) {
        if (pairs.size() == 0) {
            return s;
        }

        // 第 1 步：将任意交换的结点对输入并查集
        int len = s.length();
        UnionFind unionFind = new UnionFind(len);
        for (List pair : pairs) {
            int index1 = pair.get(0);
            int index2 = pair.get(1);
            unionFind.union(index1, index2);
        }

        // 第 2 步：构建映射关系
        char[] charArray = s.toCharArray();
        // key：连通分量的代表元，value：同一个连通分量的字符集合（保存在一个优先队列中）
        Map> hashMap = new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            hashMap.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(charArray[i]);
        }

        // 第 3 步：重组字符串
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < len; i++) {
            int root = unionFind.find(i);
            stringBuilder.append(hashMap.get(root).poll());
        }
        return stringBuilder.toString();
    }

    private class UnionFind {

        private int[] parent;
        /**
         * 以 i 为根结点的子树的高度（引入了路径压缩以后该定义并不准确）
         */
        private int[] rank;

        public UnionFind(int n) {
            this.parent = new int[n];
            this.rank = new int[n];
            for (int i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }

            if (rank[rootX] == rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                rank[rootY]++;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[rootY] = rootX;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
    }
}