题目描述
思路解析动画文字版
记住两件事:并查集连的是索引不是字符;同一组内字符可自由重排,按升序填回升序索引就最小。下面一帧帧套它。
初始 · 6 个索引各自独立：先把 6 个位置摆成 6 个节点,标号 0 到 5,对应 s 的「e d b f a c」。一开始谁也不连谁,每个索引自己是一组,所以右边连通分量个数是 6。接下来按 pairs 一对一对地连。
待处理的索引对 · [0,2] [2,4] [1,5]：这道例子的 pairs 有三对:[0,2]、[2,4]、[1,5]。也就是要把索引 0 和 2、2 和 4、1 和 5 分别连起来。索引 3 一次都没出现,等会儿它会一直孤零零。一对一对处理。
第 0 对 · 连 0 与 2：看第 0 对 [0,2]:位置 0 和位置 2 可以互换。先紫色点亮这两个索引,准备把它们并成一组。
找代表元 · 0→0, 2→2：合并前各自找代表元,也就是树根。现在 0 的根是 0、2 的根是 2,都还是自己,谁也没被并过。根不同,可以合。
合并 · 0 指向 2：按参考解的写法,让 0 的根指向 2 的根,于是 0 挂到 2 下面,这一组成了 {0,2}。连通分量从 6 降到 5。
第 1 对 · 连 2 与 4：看第 1 对 [2,4]:位置 2 和位置 4 可换。注意 2 已经带着 0 是一组了,这一步会把整组接到 4 上,传递性就体现在这。先点亮 2 和 4。
找代表元 · 2→2, 4→4：找根:2 的根是 2、4 的根是 4,都是各自树根。真正要连的是这两个根。
合并 · 2 指向 4 · 0 也跟过来：让 2 的根指向 4。现在 0 → 2 → 4 串成一棵树,根是 4,这一组变成 {0,2,4}。从没直接说 0 和 4 能换,但通过 2 这个中间人,它们被传递地连到了一起。连通分量降到 4。
第 2 对 · 连 1 与 5：看第 2 对 [1,5]:位置 1 和位置 5 可换。它们和左边那棵树没关系,是另一组。点亮 1 和 5。
找代表元 · 1→1, 5→5：找根:1 的根是 1、5 的根是 5,都还独立。根不同,可以合。
合并 · 1 指向 5：让 1 的根指向 5,这一组成了 {1,5}。现在场上有两棵树外加孤立的 3,一共 3 个连通分量。
分组定型 · {0,2,4} · {1,5} · {3}：三对全处理完,索引分成三组:{0,2,4} 一组、{1,5} 一组、索引 3 自己一组。每组内部的字符都可以自由重排,而 3 谁也连不上,它那位字符只能原地不动。下面切到字符串,逐组排序填回。
把 s 平铺成一排:索引 0 到 5 上是 e、d、b、f、a、c。现在三组的归属已经定了,我们一组一组来,先看最左边的那棵大树 {0,2,4}。
绿色点亮 {0,2,4} 这一组,把它们位置上的字符抓出来看:索引 0 是 e、索引 2 是 b、索引 4 是 a,凑成 e、b、a 三个字符。因为它们连通,这三个字符能在这三个位置上任意摆放。
把这三个字符按字典序排好:a ≤ b ≤ e。再把这一组的索引也从小到大列出来:0、2、4。接下来让最小的 a 进最小的索引 0,次小的 b 进 2,最大的 e 进 4。
把 a 写进索引 0。这是组内最小的字符,落到组内最小的位置。此刻整串是 adbfac。
把 b 写进索引 2。次小的接着放到次小的位置。此刻整串是 adbfac。
把 e 写进索引 4。组内最后一个,最大的 e 落到最大的索引 4,这一组排完了。此刻整串是 adbfec。
换第二组 {1,5}。蓝色那三位是已经排好的 {0,2,4},别再动它们。绿色点亮 1 和 5,取出字符:索引 1 是 d、索引 5 是 c,凑成 d、c。
排一下:c ≤ d。索引从小到大是 1、5。于是 c 进索引 1、d 进索引 5。原来 1 是 d、5 是 c,正好对调一下。
把 c 写进索引 1。小的 c 进小的索引 1。现在整串是 acbfec。
把 d 写进索引 5。剩下的 d 进索引 5,这一组也排完了。现在整串是 acbfed。
最后是孤零零的索引 3。它没和任何位置配过对,所属的组只有它自己,字符 f 没有任何挪动空间,只能原地保持。所以第 3 位还是 f。
六个位置全部落定:{0,2,4} 排成 a、b、e,{1,5} 排成 c、d,f 守在第 3 位。从左到右读出来就是 acbfed。每组都让小字符占了小位置,逐位都尽量小,整串就是字典序最小。
边界先想清:没有对子就原样返回;连成一整组就是把这组字符整体排序填回。
两个高频追问:可用连通分量替代并查集;填回时两个升序对齐就不会错。
参考代码
from __future__ import annotationsfrom 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 = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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))复杂度
- 时间：O((n+m)·α + n·log n)，n 是串长、m 是 pairs 个数;m 次合并、n 次查根近似线性,各组字符总量是 n,排序合计 O(n·log n)
- 空间：O(n)，parent 数组长 n,加上按组存放字符也是 n,峰值与串长同阶
易错点
面试追问把动画讲成自己的话
追问不用并查集能做吗?
追问每组排序填回,顺序会不会搞反?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
统计封闭岛屿的数目
LeetCode 1254 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题