LeetCode 1202. 交换字符串中的元素

Categories:

题目描述
思路分析
1. 解法一：并查集分组 + 组内排序（推荐）
相似题目

题目描述

✅ 1202. 交换字符串中的元素

思路分析

解法一：并查集分组 + 组内排序（推荐）

核心思路：

用并查集合并可交换的索引，形成若干连通分量。

每个分量内的索引可以任意重排，因此将该分量的字符排序后按索引升序填回。

全部分量处理完成后得到字典序最小的结果字符串。

复杂度分析：

时间复杂度：O(n log n)，分量内排序为主。

空间复杂度：O(n)，存储分量与排序缓存。

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        UnionFind uf = new UnionFind(n);
        for (List<Integer> p : pairs) {
            uf.union(p.get(0), p.get(1));
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = uf.find(i);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(i);
        }

        char[] res = s.toCharArray();
        for (List<Integer> idxs : groups.values()) {
            List<Character> chars = new ArrayList<>();
            for (int idx : idxs) {
                chars.add(res[idx]);
            }
            Collections.sort(idxs);
            Collections.sort(chars);
            for (int i = 0; i < idxs.size(); i++) {
                res[idxs.get(i)] = chars.get(i);
            }
        }

        return new String(res);
    }

    static class UnionFind {
        int[] parent;
        int[] size;

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

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

        void union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return;
            }
            if (size[ra] < size[rb]) {
                int t = ra;
                ra = rb;
                rb = t;
            }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
    }
}

import "sort"

type UnionFind struct {
    parent []int
    size   []int
}

func newUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    size := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
        size[i] = 1
    }
    return &UnionFind{parent: parent, size: size}
}

func (uf *UnionFind) find(x int) int {
    for x != uf.parent[x] {
        uf.parent[x] = uf.parent[uf.parent[x]]
        x = uf.parent[x]
    }
    return x
}

func (uf *UnionFind) union(a, b int) {
    ra := uf.find(a)
    rb := uf.find(b)
    if ra == rb {
        return
    }
    if uf.size[ra] < uf.size[rb] {
        ra, rb = rb, ra
    }
    uf.parent[rb] = ra
    uf.size[ra] += uf.size[rb]
}

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    uf := newUnionFind(n)
    for _, p := range pairs {
        uf.union(p[0], p[1])
    }

    groups := make(map[int][]int)
    for i := 0; i < n; i++ {
        root := uf.find(i)
        groups[root] = append(groups[root], i)
    }

    res := []byte(s)
    for _, idxs := range groups {
        sort.Ints(idxs)
        chars := make([]byte, len(idxs))
        for i, idx := range idxs {
            chars[i] = res[idx]
        }
        sort.Slice(chars, func(i, j int) bool {
            return chars[i] < chars[j]
        })
        for i, idx := range idxs {
            res[idx] = chars[i]
        }
    }

    return string(res)
}

相似题目

题目	难度	考察点
839. 相似字符串组	困难	并查集
721. 账户合并	中等	并查集
947. 移除最多的同行或同列石头	中等	并查集
765. 情侣牵手	困难	并查集
1579. 保证图可完全遍历	困难	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/20792212