Skip to content

Latest commit

 

History

History
271 lines (215 loc) · 7.33 KB

README.md

File metadata and controls

271 lines (215 loc) · 7.33 KB
Raw

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

English Version

题目描述

给你两个整数数组 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 <= 105
  • 1 <= source[i], target[i] <= 105
  • 0 <= allowedSwaps.length <= 105
  • allowedSwaps[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi

解法

并查集。

模板 1——朴素并查集：

# 初始化，p存储每个点的父节点
p = list(range(n))

# 返回x的祖宗节点
def find(x):
    if p[x] != x:
        # 路径压缩
        p[x] = find(p[x])
    return p[x]


# 合并a和b所在的两个集合
p[find(a)] = find(b)

模板 2——维护 size 的并查集：

# 初始化，p存储每个点的父节点，size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
p = list(range(n))
size = [1] * n

# 返回x的祖宗节点
def find(x):
    if p[x] != x:
        # 路径压缩
        p[x] = find(p[x])
    return p[x]

# 合并a和b所在的两个集合
if find(a) != find(b):
    size[find(b)] += size[find(a)]
    p[find(a)] = find(b)

模板 3——维护到祖宗节点距离的并查集：

# 初始化，p存储每个点的父节点，d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n

# 返回x的祖宗节点
def find(x):
    if p[x] != x:
        t = find(p[x])
        d[x] += d[p[x]]
        p[x] = t
    return p[x]

# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distance

Python3

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n = len(source)
        p = list(range(n))

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for i, j in allowedSwaps:
            p[find(i)] = find(j)

        mp = defaultdict(Counter)
        for i in range(n):
            mp[find(i)][source[i]] += 1
        res = 0
        for i in range(n):
            if mp[find(i)][target[i]] > 0:
                mp[find(i)][target[i]] -= 1
            else:
                res += 1
        return res

Java

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[] e : allowedSwaps) {
            p[find(e[0])] = find(e[1]);
        }
        Map<Integer, Map<Integer, Integer>> mp = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            mp.computeIfAbsent(root, k -> new HashMap<>())
                .put(source[i], mp.get(root).getOrDefault(source[i], 0) + 1);
        }
        int res = 0;
        for (int i = 0; i < n; ++i) {
            int root = find(i);
            if (mp.get(root).getOrDefault(target[i], 0) > 0) {
                mp.get(root).put(target[i], mp.get(root).get(target[i]) - 1);
            } else {
                ++res;
            }
        }
        return res;
    }

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

C++

class Solution {
public:
    vector<int> p;

    int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
        int n = source.size();
        p.resize(n);
        for (int i = 0; i < n; ++i) p[i] = i;
        for (auto e : allowedSwaps) p[find(e[0])] = find(e[1]);
        unordered_map<int, unordered_map<int, int>> mp;
        for (int i = 0; i < n; ++i) ++mp[find(i)][source[i]];
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (mp[find(i)][target[i]] > 0)
                --mp[find(i)][target[i]];
            else
                ++res;
        }
        return res;
    }

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

Go

var p []int

func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int {
	n := len(source)
	p = make([]int, n)
	for i := 0; i < n; i++ {
		p[i] = i
	}
	for _, e := range allowedSwaps {
		p[find(e[0])] = find(e[1])
	}
	mp := make(map[int]map[int]int)
	for i := 0; i < n; i++ {
		if mp[find(i)] == nil {
			mp[find(i)] = make(map[int]int)
		}
		mp[find(i)][source[i]]++
	}
	res := 0
	for i := 0; i < n; i++ {
		if mp[find(i)][target[i]] > 0 {
			mp[find(i)][target[i]]--
		} else {
			res++
		}
	}
	return res
}

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

...