What is the main pattern in Minimize Hamming Distance After Swap Operations?

The core pattern is connected components over array indices, followed by frequency matching inside each component. The graph can be traversed with DFS or built with Union Find.

Why can values be freely rearranged inside one component?

Because swaps can be repeated in any order, any index reachable through allowedSwaps belongs to the same connected group. Within that group, values can be permuted arbitrarily through a sequence of valid swaps.

Why does counting frequencies work better than simulating swaps?

The exact swap sequence does not matter once you know the component. What matters is how many copies of each value source has in that component and how many copies target needs there.

When would Union Find be better than DFS here?

Union Find is often cleaner when you want to merge many swap pairs without storing a full adjacency list. DFS is equally valid and sometimes easier to explain when the interviewer emphasizes the graph view.

What happens when allowedSwaps is empty?

Each index becomes its own component, so no value can move. The answer is then just the ordinary Hamming distance between source and target.

#1722

Medium

auto_awesome图·搜索

LeetCode 题解工作台

执行交换操作后的最小汉明距离

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [a i , b i ] 表示你可以交换数组 source 中下标为 a i 和 b i （下标从 0 开始）的两个元素。注意，你可以按任…

数组深度优先搜索并查集

题目描述

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [a_i, b_i] 表示你可以交换数组 source 中下标为 a_i 和 b_i（下标从 0 开始）的两个元素。注意，你可以按任意顺序多次交换一对特定下标指向的元素。

相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。

在对数组 source 执行任意数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。

示例 1：

输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。

示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。

示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

提示：

n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i

lightbulb

解题思路

方法一：并查集 + 哈希表

我们可以将每个下标看作一个节点，每个下标对应的元素看作节点的值，那么给定的 allowedSwaps 中的每个元素 [a_i, b_i] 就表示下标 a_i 和 b_i 之间存在一条边。因此，我们可以使用并查集来维护这些连通分量。

在得到每个连通分量之后，我们再用二维哈希表 $cnt$ 分别统计每个连通分量中每个元素出现的次数，最后对于数组 target 中的每个元素，如果其在对应的连通分量中出现的次数大于 0，则将其出现次数减 1，否则将答案加 1。

时间复杂度 $O(n \times \log n)$ 或 $O(n \times \alpha(n))$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度，而 $\alpha$ 是阿克曼函数的反函数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They hint that allowedSwaps forms a graph over indices, which is the push toward connected components.
question_mark
They ask why repeated swaps matter, which is testing whether you realize each component allows arbitrary reordering.
question_mark
They ask for a faster method than simulating swaps, which means you should switch to component-level frequency matching.

warning

常见陷阱

外企场景

error
Trying to greedily swap mismatched positions one by one misses the real invariant that only component membership matters.
error
Comparing indices directly inside a component instead of comparing value counts overcounts mismatches that can actually be fixed by reordering.
error
Forgetting isolated indices as single-node components causes missing mismatches when allowedSwaps is sparse or empty.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Replace DFS with Union Find and keep the same per-component counting logic.
arrow_right_alt
Return the indices that must remain mismatched instead of only the minimum Hamming distance.
arrow_right_alt
Handle online swap additions by rebuilding or maintaining components before re-running the matching step.

help

常见问题

外企场景

继续练习

#1631 最小体力消耗路径 #1559 二维网格图中探测环 #1905 统计子岛屿