交换字符串中的元素 图解题解

这道题到底在问什么

输入

s="dcab", pairs=[[0,3],[1,2]]

输出

"bacd" (两组:{0,3} 和 {1,2})

输入

s="dcab", pairs=[[0,3],[1,2],[0,2]]

输出

"abcd" (多了 [0,2] 把两组并成一组)

最优解：一步一步想明白

1. 3记住两件事:并查集连的是索引不是字符;同一组内字符可自由重排,按升序填回升序索引就最小。下面一帧帧套它。
2. 4连通分量 = 6先把 6 个位置摆成 6 个节点,标号 0 到 5,对应 s 的「e d b f a c」。一开始谁也不连谁,每个索引自己是一组,所以右边连通分量个数是 6。接下来按 pairs 一对一对地连。
3. 5pairs = [[0,2],[2,4],[1,5]]这道例子的 pairs 有三对:[0,2]、[2,4]、[1,5]。也就是要把索引 0 和 2、2 和 4、1 和 5 分别连起来。索引 3 一次都没出现,等会儿它会一直孤零零。一对一对处理。
4. 6准备合并索引 0 和 2看第 0 对 [0,2]:位置 0 和位置 2 可以互换。先紫色点亮这两个索引,准备把它们并成一组。
5. 7代表 0 与 2合并前各自找代表元,也就是树根。现在 0 的根是 0、2 的根是 2,都还是自己,谁也没被并过。根不同,可以合。
6. 8连通分量 = 5按参考解的写法,让 0 的根指向 2 的根,于是 0 挂到 2 下面,这一组成了 {0,2}。连通分量从 6 降到 5。
7. 9准备合并索引 2 和 4看第 1 对 [2,4]:位置 2 和位置 4 可换。注意 2 已经带着 0 是一组了,这一步会把整组接到 4 上,传递性就体现在这。先点亮 2 和 4。
8. 10代表 2 与 4找根:2 的根是 2、4 的根是 4,都是各自树根。真正要连的是这两个根。
9. 11连通分量 = 4让 2 的根指向 4。现在 0 → 2 → 4 串成一棵树,根是 4,这一组变成 {0,2,4}。从没直接说 0 和 4 能换,但通过 2 这个中间人,它们被传递地连到了一起。连通分量降到 4。
10. 12准备合并索引 1 和 5看第 2 对 [1,5]:位置 1 和位置 5 可换。它们和左边那棵树没关系,是另一组。点亮 1 和 5。
11. 13代表 1 与 5找根:1 的根是 1、5 的根是 5,都还独立。根不同,可以合。
12. 14连通分量 = 3让 1 的根指向 5,这一组成了 {1,5}。现在场上有两棵树外加孤立的 3,一共 3 个连通分量。
13. 15三组就绪三对全处理完,索引分成三组:{0,2,4} 一组、{1,5} 一组、索引 3 自己一组。每组内部的字符都可以自由重排,而 3 谁也连不上,它那位字符只能原地不动。下面切到字符串,逐组排序填回。
14. 16把 s 平铺成一排:索引 0 到 5 上是 e、d、b、f、a、c。现在三组的归属已经定了,我们一组一组来,先看最左边的那棵大树 {0,2,4}。
15. 17绿色点亮 {0,2,4} 这一组,把它们位置上的字符抓出来看:索引 0 是 e、索引 2 是 b、索引 4 是 a,凑成 e、b、a 三个字符。因为它们连通,这三个字符能在这三个位置上任意摆放。
16. 18把这三个字符按字典序排好:a ≤ b ≤ e。再把这一组的索引也从小到大列出来:0、2、4。接下来让最小的 a 进最小的索引 0,次小的 b 进 2,最大的 e 进 4。
17. 19把 a 写进索引 0。这是组内最小的字符,落到组内最小的位置。此刻整串是 adbfac。
18. 20把 b 写进索引 2。次小的接着放到次小的位置。此刻整串是 adbfac。
19. 21把 e 写进索引 4。组内最后一个,最大的 e 落到最大的索引 4,这一组排完了。此刻整串是 adbfec。
20. 22换第二组 {1,5}。蓝色那三位是已经排好的 {0,2,4},别再动它们。绿色点亮 1 和 5,取出字符:索引 1 是 d、索引 5 是 c,凑成 d、c。
21. 23排一下:c ≤ d。索引从小到大是 1、5。于是 c 进索引 1、d 进索引 5。原来 1 是 d、5 是 c,正好对调一下。
22. 24把 c 写进索引 1。小的 c 进小的索引 1。现在整串是 acbfec。
23. 25把 d 写进索引 5。剩下的 d 进索引 5,这一组也排完了。现在整串是 acbfed。
24. 26最后是孤零零的索引 3。它没和任何位置配过对,所属的组只有它自己,字符 f 没有任何挪动空间,只能原地保持。所以第 3 位还是 f。
25. 27六个位置全部落定:{0,2,4} 排成 a、b、e,{1,5} 排成 c、d,f 守在第 3 位。从左到右读出来就是 acbfed。每组都让小字符占了小位置,逐位都尽量小,整串就是字典序最小。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(s)
        p = list(range(n))
        for a, b in pairs:
            p[find(a)] = find(b)
        d = defaultdict(list)
        for i, c in enumerate(s):
            d[find(i)].append(c)
        for i in d.keys():
            d[i].sort(reverse=True)
        return "".join(d[find(i)].pop() for i in range(n))

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        int p[n];
        iota(p, p + n, 0);
        vector<char> d[n];
        function<int(int)> find = [&](int x) -> int {
            if (p[x] != x) {
                p[x] = find(p[x]);
            }
            return p[x];
        };
        for (auto e : pairs) {
            int a = e[0], b = e[1];
            p[find(a)] = find(b);
        }
        for (int i = 0; i < n; ++i) {
            d[find(i)].push_back(s[i]);
        }
        for (auto& e : d) {
            sort(e.rbegin(), e.rend());
        }
        for (int i = 0; i < n; ++i) {
            auto& e = d[find(i)];
            s[i] = e.back();
            e.pop_back();
        }
        return s;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int[] p;

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        int n = s.length();
        p = new int[n];
        List<Character>[] d = new List[n];
        for (int i = 0; i < n; ++i) {
            p[i] = i;
            d[i] = new ArrayList<>();
        }
        for (List<Integer> pair : pairs) {
            int a = pair.get(0), b = pair.get(1);
            p[find(a)] = find(b);
        }
        char[] cs = s.toCharArray();
        for (int i = 0; i < n; ++i) {
            d[find(i)].add(cs[i]);
        }
        for (List<Character> e : d) {
            e.sort((a, b) -> b - a);
        }
        for (int i = 0; i < n; ++i) {
            List<Character> e = d[find(i)];
            cs[i] = e.remove(e.size() - 1);
        }
        return String.valueOf(cs);
    }

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

复杂度

面试官可能追问