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

这道题到底在问什么

输入

source=[1,2,3,4], target=[2,1,4,5], swaps=[[0,1],[2,3]]

输出

1 (两组各自重排,只剩下标 3 的 4 配不出 5)

输入

source=[1,2,3,4], target=[1,3,2,4], swaps=[]

输出

2 (不能交换,下标 1、2 直接不同)

最优解：一步一步想明白

1. 3记牢两件事:并查集连的是下标不是数值;同组只需比「值的可重集合」是否相等,凑不齐几个就差几位。下面一帧帧套它。
2. 4连通分量 = 6先把 6 个下标摆成 6 个节点,标号 0 到 5,对应 source 的 40、20、70、50、30、80。一开始谁也不连谁,每个下标自己是一组,所以右边连通分量个数是 6。接下来按 allowedSwaps 一对一对地连。
3. 5allowedSwaps = [[0,1],[1,2],[3,4]]这道例子的 allowedSwaps 有三对:[0,1]、[1,2]、[3,4]。也就是把下标 0 和 1、1 和 2、3 和 4 分别连起来。下标 5 一次都没出现,等会儿它会一直孤零零。一对一对处理。
4. 6准备合并下标 0 和 1看第 0 对 [0,1]:下标 0 和下标 1 上的数可以互换。先紫色点亮这两个下标,准备把它们并成一组。
5. 7代表 0 与 1合并前各自找代表元,也就是树根。现在 0 的根是 0、1 的根是 1,都还是自己,谁也没被并过。根不同,可以合。
6. 8连通分量 = 5按参考解的写法,让 0 的根指向 1 的根,于是 0 挂到 1 下面,这一组成了 {0,1}。连通分量从 6 降到 5。
7. 9准备合并下标 1 和 2看第 1 对 [1,2]:下标 1 和下标 2 可换。注意 1 已经带着 0 是一组了,这一步会把整组接到 2 上,传递性就在这里体现。先点亮 1 和 2。
8. 10代表 1 与 2找根:1 的根是 1、2 的根是 2,都是各自树根。真正要连的是这两个根。
9. 11连通分量 = 4让 1 的根指向 2。现在 0 → 1 → 2 串成一棵树,根是 2,这一组变成 {0,1,2}。从没直接说 0 和 2 能换,但通过 1 这个中间人,它们被传递地连到了一起。连通分量降到 4。
10. 12准备合并下标 3 和 4看第 2 对 [3,4]:下标 3 和下标 4 可换。它们和左边那棵树没关系,是另一组。点亮 3 和 4。
11. 13代表 3 与 4找根:3 的根是 3、4 的根是 4,都还独立。根不同,可以合。
12. 14连通分量 = 3让 3 的根指向 4,这一组成了 {3,4}。现在场上有两棵树,外加孤立的下标 5,一共 3 个连通分量。
13. 15三组就绪三对全处理完,下标分成三组:{0,1,2} 一组、{3,4} 一组、下标 5 自己一组。每组内部的数都能自由重排,而 5 谁也连不上,它那位只能原地不动。下面切到数组,逐组比对值的多重集。
14. 16把 source 平铺成一排:40、20、70、50、30、80。三组归属已定,A 组是下标 0、1、2,B 组是下标 3、4,C 组只有下标 5。右边面板按「组·值」记每个值的个数。我们先扫一遍 source 把各组的值数清楚。
15. 17看 source 第 0 位,值是 40,它属于组 A。在面板里给「组 A 的 40」记上一笔,现在这一项的个数是 1。继续往后数。
16. 18看 source 第 1 位,值是 20,它属于组 A。在面板里给「组 A 的 20」记上一笔,现在这一项的个数是 1。继续往后数。
17. 19看 source 第 2 位,值是 70,它属于组 A。在面板里给「组 A 的 70」记上一笔,现在这一项的个数是 1。继续往后数。
18. 20看 source 第 3 位,值是 50,它属于组 B。在面板里给「组 B 的 50」记上一笔,现在这一项的个数是 1。继续往后数。
19. 21看 source 第 4 位,值是 30,它属于组 B。在面板里给「组 B 的 30」记上一笔,现在这一项的个数是 1。继续往后数。
20. 22看 source 第 5 位,值是 80,它属于组 C。在面板里给「组 C 的 80」记上一笔,现在这一项的个数是 1。source 一遍扫完,三组的值都数清了,接下来换 target 来抵消。
21. 23换上 target:20、70、40、50、90、10。规则是逐位看 target,在它所属组的面板里把这个值减一。如果某个值本来就没有、或已经被减到 0,再减就成了负数,说明组里没有它的备货,这一位注定不同,答案加一。开始逐位抵消。
22. 24看 target 第 0 位,值是 20,属于组 A。面板里组 A 正好有 20,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
23. 25看 target 第 1 位,值是 70,属于组 A。面板里组 A 正好有 70,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
24. 26看 target 第 2 位,值是 40,属于组 A。面板里组 A 正好有 40,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
25. 27看 target 第 3 位,值是 50,属于组 B。面板里组 B 正好有 50,减一抵消,个数变回 0。这一位能靠组内重排对上,不计入不同。
26. 28看 target 第 4 位,值是 90,属于组 B。可面板里组 B 根本没有 90 可减,一减就成了负数。说明这一组的 source 里凑不出 90,第 4 位只能保持不同,答案累加到 1。
27. 29看 target 第 5 位,值是 10,属于组 C。可面板里组 C 根本没有 10 可减,一减就成了负数。说明这一组的 source 里凑不出 10,第 5 位只能保持不同,答案累加到 2。
28. 30target 逐位扫完。组 A 的三个值和 source 完全是同一套,靠交换重排全部对上,0 处不同。组 B 里 source 的 30 配不出 target 的 90,差 1 处。孤立的下标 5,source 的 80 换不动,对不上 target 的 10,再差 1 处。红色标出的就是这两位。合起来最小汉明距离是 2,和开头说的对上了。

⚠️ 容易写错的地方

完整代码（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 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#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;
class Solution {
public:
    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        function<int(int)> find = [&](int x) {
            return x == p[x] ? x : p[x] = find(p[x]);
        };
        for (auto& a : allowedSwaps) {
            p[find(a[0])] = find(a[1]);
        }
        unordered_map<int, unordered_map<int, int>> cnt;
        for (int i = 0; i < n; ++i) {
            ++cnt[find(i)][source[i]];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (--cnt[find(i)][target[i]] < 0) {
                ++ans;
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    private int[] p;

    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int n = source.length;
        p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        for (int[] a : allowedSwaps) {
            p[find(a[0])] = find(a[1]);
        }
        Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int j = find(i);
            cnt.computeIfAbsent(j, k -> new HashMap<>()).merge(source[i], 1, Integer::sum);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int j = find(i);
            Map<Integer, Integer> t = cnt.get(j);
            if (t.merge(target[i], -1, Integer::sum) < 0) {
                ++ans;
            }
        }
        return ans;
    }

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

复杂度

面试官可能追问