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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 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 <= ai, bi <= n - 1
ai != bi

# 思路

查并集

# 解法

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        int res = 0;
        int n = source.length;
        UnionFindSet unionFindSet = new UnionFindSet(n);
        for(int[] arr : allowedSwaps) 
            unionFindSet.union(arr[0], arr[1]);
        //<当前元素, 当前元素的索引的集合>
        Map<Integer, List<Integer>> map = new HashMap<>();

        //遍历target数组
        for(int i = 0; i < n; i++) {
            //记录target元素以及索引
            //因为可能会出现重复元素所以用List集合
            List<Integer> list = map.getOrDefault(target[i], new LinkedList<>());
            list.add(i);
            map.put(target[i], list);
        }
        
        //遍历source数组
        for(int i = 0; i < n; i++) {
            int num = source[i];
            //source的数字num在target中找不到
            if(!map.containsKey(num)) {
                res++;
            }else {
            //source的数字num在target中可以找到
                //默认不在在一个连通器内
                boolean flag = false;
                List<Integer> list = map.get(num);
                //遍历num在target中的索引
                for(int j = 0; j < list.size(); j++) {
                    //当前索引
                    int index = list.get(j);
                    //source[i]可以通过若干操作移到与之相等的source[index]
                    if(unionFindSet.isConnected(i, index)) {
                        //移除index
                        list.remove(j);
                        map.put(num, list);
                        //在一个连通器内
                        flag = true;
                        break;
                    }
                }
                //所有的index都尝试了还是false
                //果断+1
                if(!flag)
                    res++;
            }
        }
        return res;
    }
}

//并查集
public class UnionFindSet {
    private int[] parent;
    private int n;
    public UnionFindSet(int n) {
        this.n = n;
        this.parent = new int[n];
        //初始化
        //自己和自己联通
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }

    //找到x的根节点
    public int find(int x) {
        if(x == parent[x])
            return x;
        //路径压缩
        parent[x] = find(parent[x]);
        return parent[x];
    }

    public void union(int x, int y) {
        int index1 = find(x), index2 = find(y);
        if(index1 == index2)
            return;
        parent[index1] = index2;
    }

    //判断是否连通
    public boolean isConnected(int x, int y) {
    return find(x) == find(y);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

# 总结

分析出几种情况，然后分别对各个情况实现

#Java