交换字符串中的元素

LeetCode每日一题，1202. Smallest String With Swaps

先看题目描述

大意就是给定一个字符串 s，数组 pairs 代表字符串的多个索引对，我们可以任意次数的交换索引对中索引对应的字母，让我们返回经交换后可以得到的最小字符串

算法思路

并查集

我们将可以互相交换的字符视为一个连通分量，一个连通分量内的字符可以任意的互相交换位置。于是我们可以通过给定的字符串 s 和数组 pairs，求出字符串的各连通分量，将各连通分量内的字符按照升序排列后，将字符串重新组装起来，然后返回组装的字符串即可

求连通分量我们可以通过并查集完成，而将连通分量内的字符按照升序排列，我们可以使用小根堆自动完成升序排列的过程

算法源码

并查集

将并查集部分的代码写好后，发现后面不知道该怎么写了，于是去看题解，才知道后面该怎么求连通分量，以及可以使用小根堆来将连通分量内字符自动按照升序排列，map.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(cs[i]) 这种写法也是第一次见，值得学习

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
        for (List<Integer> pair : pairs) {
            int a = pair.get(0);
            int b = pair.get(1);
            union(a, b, parent, rank);
        }
        char[] cs = s.toCharArray();
        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = find(i, parent);
            /*
            if (map.containsKey(root)) {
                map.get(root).offer(cs[i]);
            } else {
                PriorityQueue prior = new PriorityQueue();
                prior.offer(cs[i]);
                map.put(root, prior);
            }
            */
            // 上面六行代码等价于下面一行代码，JDK 1.8 以及以后支持下面的写法
            map.computeIfAbsent(root, key -> new PriorityQueue<>()).offer(cs[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int root = find(i, parent);
            sb.append(map.get(root).poll());
        }
        return sb.toString();
    }

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

    private void union(int a, int b, int[] parent, int[] rank) {
        int x = find(a, parent);
        int y = find(b, parent);
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
        }
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}