Union并集

交换字符串中的元素

• 使用数组求并集的技巧见ArrayUnion类

 private static final int MAX = 100000;

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        // 并集分类
        ArrayUnion union = new ArrayUnion(MAX);
        for (List<Integer> pair : pairs) {
            union.union(pair.get(0), pair.get(1));
        }
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            int key = union.find(i);
            if (map.containsKey(key)) {
                map.get(key).add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(key, list);
            }
        }
        // 排序
        char[] ans = new char[s.length()];
        for (List<Integer> indexList : map.values()) {
            char[] chars = new char[indexList.size()];
            int i = 0;
            for (int index : indexList) {
                chars[i++] = (s.charAt(index));
            }
            Arrays.sort(chars);
            // Collections.sort(indexList); // indexList本来就是排好序的
            i = 0;
            for (Integer index : indexList) {
                ans[index] = chars[i++];
            }
        }
        return new String(ans);
    }

    static class ArrayUnion {
        int[] parent;

        public ArrayUnion(int len) {
            parent = new int[len];
            for (int i = 0; i < len; ++i)
                parent[i] = i;
        }

        public int find(int x) {
            return parent[x] != x ? parent[x] = find(parent[x]) : x; // 这里给parent[x]赋值是为了后面利用数组计算并集时，减少求key时find(x)递归调用的深度，不赋值，速度将会减慢
        }

        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }