java 解法, 执行用时: 42 ms, 内存消耗: 91.5 MB, 提交时间: 2023-06-06 10:09:35

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        DisjointSetUnion dsu = new DisjointSetUnion(s.length());
        for (List<Integer> pair : pairs) {
            dsu.unionSet(pair.get(0), pair.get(1));
        }
        Map<Integer, List<Character>> map = new HashMap<Integer, List<Character>>();
        for (int i = 0; i < s.length(); i++) {
            int parent = dsu.find(i);
            if (!map.containsKey(parent)) {
                map.put(parent, new ArrayList<Character>());
            }
            map.get(parent).add(s.charAt(i));
        }
        for (Map.Entry<Integer, List<Character>> entry : map.entrySet()) {
            Collections.sort(entry.getValue(), new Comparator<Character>() {
                public int compare(Character c1, Character c2) {
                    return c2 - c1;
                }
            });
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            int x = dsu.find(i);
            List<Character> list = map.get(x);
            sb.append(list.remove(list.size() - 1));
        }
        return sb.toString();
    }
}

class DisjointSetUnion {
    int[] f;
    int[] rank;
    int n;

    public DisjointSetUnion(int n) {
        this.n = n;
        rank = new int[n];
        Arrays.fill(rank, 1);
        f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    public int find(int x) {
        return f[x] == x ? x : (f[x] = find(f[x]));
    }

    public void unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            return;
        }
        if (rank[fx] < rank[fy]) {
            int temp = fx;
            fx = fy;
            fy = temp;
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
    }
}

golang 解法, 执行用时: 92 ms, 内存消耗: 18.3 MB, 提交时间: 2023-06-06 10:09:20

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    fa := make([]int, n)
    rank := make([]int, n)
    for i := range fa {
        fa[i] = i
        rank[i] = 1
    }
    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }
    union := func(x, y int) {
        fx, fy := find(x), find(y)
        if fx == fy {
            return
        }
        if rank[fx] < rank[fy] {
            fx, fy = fy, fx
        }
        rank[fx] += rank[fy]
        fa[fy] = fx
    }

    for _, p := range pairs {
        union(p[0], p[1])
    }

    groups := map[int][]byte{}
    for i := range s {
        f := find(i)
        groups[f] = append(groups[f], s[i])
    }

    for _, bytes := range groups {
        sort.Slice(bytes, func(i, j int) bool { return bytes[i] < bytes[j] })
    }

    ans := make([]byte, n)
    for i := range ans {
        f := find(i)
        ans[i] = groups[f][0]
        groups[f] = groups[f][1:]
    }
    return string(ans)
}

javascript 解法, 执行用时: 204 ms, 内存消耗: 74.6 MB, 提交时间: 2023-06-06 10:08:55

/**
 * @param {string} s
 * @param {number[][]} pairs
 * @return {string}
 */
var smallestStringWithSwaps = function(s, pairs) {
    const fa = new Array(100010).fill(0);

    const find = (x) => {
        return x === fa[x] ? x : fa[x] = find(fa[x]);
    }

    const n = s.length;
    for (let i = 0; i < n; i++) {
        fa[i] = i;
    }
    for (let i = 0; i < pairs.length; ++i) {
        const x = pairs[i][0], y = pairs[i][1];
        const ux = find(x), uy = find(y);
        if (ux ^ uy) {
            fa[ux] = uy;
        }
    }

    const vec = new Array(n).fill(0).map(() => new Array());
    for (let i = 0; i < n; i++) {
        fa[i] = find(i);
        vec[fa[i]].push(s[i]);
    }

    for (let i = 0; i < n; ++i) { 
        if (vec[i].length > 0) {
            vec[i].sort((a, b) => a.charCodeAt() - b.charCodeAt());
        }
    }
    const p = new Array(n).fill(0);
    let ans = [];
    for (let i = 0; i < n; ++i) {
        ans.push('1');
    }

    for (let i = 0; i < n; ++i) {
        ans[i] = vec[fa[i]][p[fa[i]]];
        p[fa[i]]++;
    }
    
    return ans.join('');
};

python3 解法, 执行用时: 244 ms, 内存消耗: 40.8 MB, 提交时间: 2023-06-06 10:08:40

# 并查集
class DisjointSetUnion:
    def __init__(self, n: int):
        self.n = n
        self.rank = [1] * n
        self.f = list(range(n))
    
    def find(self, x: int) -> int:
        if self.f[x] == x:
            return x
        self.f[x] = self.find(self.f[x])
        return self.f[x]
    
    def unionSet(self, x: int, y: int):
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return
        if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
        self.rank[fx] += self.rank[fy]
        self.f[fy] = fx
        
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        dsu = DisjointSetUnion(len(s))
        for x, y in pairs:
            dsu.unionSet(x, y)
        
        mp = collections.defaultdict(list)
        for i, ch in enumerate(s):
            mp[dsu.find(i)].append(ch)
        
        for vec in mp.values():
            vec.sort(reverse=True)
        
        ans = list()
        for i in range(len(s)):
            x = dsu.find(i)
            ans.append(mp[x][-1])
            mp[x].pop()
        
        return "".join(ans)