题目描述
思路解析动画文字版
记牢两件事:并查集连的是下标不是数值;同组只需比「值的可重集合」是否相等,凑不齐几个就差几位。下面一帧帧套它。
初始 · 6 个下标各自独立：先把 6 个下标摆成 6 个节点,标号 0 到 5,对应 source 的 40、20、70、50、30、80。一开始谁也不连谁,每个下标自己是一组,所以右边连通分量个数是 6。接下来按 allowedSwaps 一对一对地连。
待处理的索引对 · [0,1] [1,2] [3,4]：这道例子的 allowedSwaps 有三对:[0,1]、[1,2]、[3,4]。也就是把下标 0 和 1、1 和 2、3 和 4 分别连起来。下标 5 一次都没出现,等会儿它会一直孤零零。一对一对处理。
第 0 对 · 连 0 与 1：看第 0 对 [0,1]:下标 0 和下标 1 上的数可以互换。先紫色点亮这两个下标,准备把它们并成一组。
找代表元 · 0→0, 1→1：合并前各自找代表元,也就是树根。现在 0 的根是 0、1 的根是 1,都还是自己,谁也没被并过。根不同,可以合。
合并 · 0 指向 1：按参考解的写法,让 0 的根指向 1 的根,于是 0 挂到 1 下面,这一组成了 {0,1}。连通分量从 6 降到 5。
第 1 对 · 连 1 与 2：看第 1 对 [1,2]:下标 1 和下标 2 可换。注意 1 已经带着 0 是一组了,这一步会把整组接到 2 上,传递性就在这里体现。先点亮 1 和 2。
找代表元 · 1→1, 2→2：找根:1 的根是 1、2 的根是 2,都是各自树根。真正要连的是这两个根。
合并 · 1 指向 2 · 0 也跟过来：让 1 的根指向 2。现在 0 → 1 → 2 串成一棵树,根是 2,这一组变成 {0,1,2}。从没直接说 0 和 2 能换,但通过 1 这个中间人,它们被传递地连到了一起。连通分量降到 4。
第 2 对 · 连 3 与 4：看第 2 对 [3,4]:下标 3 和下标 4 可换。它们和左边那棵树没关系,是另一组。点亮 3 和 4。
找代表元 · 3→3, 4→4：找根:3 的根是 3、4 的根是 4,都还独立。根不同,可以合。
合并 · 3 指向 4：让 3 的根指向 4,这一组成了 {3,4}。现在场上有两棵树,外加孤立的下标 5,一共 3 个连通分量。
分组定型 · {0,1,2} · {3,4} · {5}：三对全处理完,下标分成三组:{0,1,2} 一组、{3,4} 一组、下标 5 自己一组。每组内部的数都能自由重排,而 5 谁也连不上,它那位只能原地不动。下面切到数组,逐组比对值的多重集。
把 source 平铺成一排:40、20、70、50、30、80。三组归属已定,A 组是下标 0、1、2,B 组是下标 3、4,C 组只有下标 5。右边面板按「组·值」记每个值的个数。我们先扫一遍 source 把各组的值数清楚。
看 source 第 0 位,值是 40,它属于组 A。在面板里给「组 A 的 40」记上一笔,现在这一项的个数是 1。继续往后数。
看 source 第 1 位,值是 20,它属于组 A。在面板里给「组 A 的 20」记上一笔,现在这一项的个数是 1。继续往后数。
看 source 第 2 位,值是 70,它属于组 A。在面板里给「组 A 的 70」记上一笔,现在这一项的个数是 1。继续往后数。
看 source 第 3 位,值是 50,它属于组 B。在面板里给「组 B 的 50」记上一笔,现在这一项的个数是 1。继续往后数。
看 source 第 4 位,值是 30,它属于组 B。在面板里给「组 B 的 30」记上一笔,现在这一项的个数是 1。继续往后数。
看 source 第 5 位,值是 80,它属于组 C。在面板里给「组 C 的 80」记上一笔,现在这一项的个数是 1。source 一遍扫完,三组的值都数清了,接下来换 target 来抵消。
换上 target:20、70、40、50、90、10。规则是逐位看 target,在它所属组的面板里把这个值减一。如果某个值本来就没有、或已经被减到 0,再减就成了负数,说明组里没有它的备货,这一位注定不同,答案加一。开始逐位抵消。
看 target 第 0 位,值是 20,属于组 A。面板里组 A 正好有 20,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
看 target 第 1 位,值是 70,属于组 A。面板里组 A 正好有 70,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
看 target 第 2 位,值是 40,属于组 A。面板里组 A 正好有 40,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
看 target 第 3 位,值是 50,属于组 B。面板里组 B 正好有 50,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
看 target 第 4 位,值是 90,属于组 B。可面板里组 B 根本没有 90 可减,一减就成了负数。说明这一组的 source 里凑不出 90,第 4 位只能保持不同,答案累加到 1。
看 target 第 5 位,值是 10,属于组 C。可面板里组 C 根本没有 10 可减,一减就成了负数。说明这一组的 source 里凑不出 10,第 5 位只能保持不同,答案累加到 2。
target 逐位扫完。组 A 的三个值和 source 完全是同一套,靠交换重排全部对上,0 处不同。组 B 里 source 的 30 配不出 target 的 90,差 1 处。孤立的下标 5,source 的 80 换不动,对不上 target 的 10,再差 1 处。红色标出的就是这两位。合起来最小汉明距离是 2,和开头说的对上了。
边界先想清:无索引对就退化成原始汉明距离;全连通且值多重集相同就是 0。
两个高频追问:可用连通分量替代并查集;同组比值的多重集即得最少不同位。
参考代码
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 Solution: def minimumHammingDistance( self, source: List[int], target: List[int], allowedSwaps: List[List[int]] ) -> int: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] n = len(source) p = list(range(n)) for a, b in allowedSwaps: p[find(a)] = find(b) cnt = defaultdict(Counter) for i, x in enumerate(source): j = find(i) cnt[j][x] += 1 ans = 0 for i, x in enumerate(target): j = find(i) cnt[j][x] -= 1 ans += cnt[j][x] < 0 return ans复杂度
- 时间：O((n + m)·α(n))，n 是数组长、m 是 allowedSwaps 个数;m 次合并加两遍各 n 次查根,带路径压缩近似线性,α 是反阿克曼几乎是常数
- 空间：O(n)，parent 数组长 n,组到值的计数表里键值总量也不超过 n,峰值与数组同阶
易错点
面试追问把动画讲成自己的话
追问不用并查集能做吗?
追问为什么同组只看值的多重集相不相等,就能得出这组的最少不同位?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
重新排列后的最大子矩阵
LeetCode 1727 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题