题目描述
[1722] 执行交换操作后的最小汉明距离
https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/
给你两个整数数组 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^5
1 <= source[i], target[i] <= 10^5
0 <= allowedSwaps.length <= 10^5
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi
题目剖析&信息挖掘
题目考查的是图连通块的查找，可以使用并查集或者深度优先遍历实现。并查集更加简便，我使用的是并查集。
并查集还不会？赶紧来学习吧并查集学习资料
解题思路
方法一 并查集+哈希+贪心
分析
首先，可以发现一个规律。
交换关系具有传递性。即如果a与b可以交换，b与c可以交换，那么a,b,c可以两两相互交换。(自己模拟一下就知道)
那么对于给定allowedSwaps可以找出相互关系的一组数据（在图中称为连通块）。
一个连通块与其他连通块是不能进行交换。
题目目要求汉明距离最小，那么我们希望通过交换可以使最多的数据都对应上。
找到一个连通快后，利用哈希算法去查询最大配对数(pairs)。
len(target)-pairs即为答案
思路
func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int {
us := UnionFindSet{}
us.InitUnionSet(len(target)+2)
// 合并所人相关数据
for _, v := range allowedSwaps{
us.Union(v[0], v[1])
}
set := make([][]int, len(target)) // 保存以为个结点为根的集合，不一定都有元素
// 将一个连通块内的数据收集起来
for i:=0;i<len(target);i++ {
f := us.FindV2(i)
if set[f] == nil {set[f] = []int{}}
set[f] = append(set[f], i)
}
sum :=0
// 查询最大配对数
for _, s := range set {
sum += getSameNum(source, target, s)
}
return len(target)-sum // 总数-配对数
}
注意
- 数字是有重复的。
- 查询的是最大配对数，不是最终结果。
知识点
- 并查集
- 哈希
- 连通块
- 贪心
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
参考
代码实现
/*
并查集，判连通用
*/
type UnionFindSet struct {
father []int // 存储结点的父亲
nodeNum int // 总结点个数
}
func (us *UnionFindSet) InitUnionSet(n int) {
us.nodeNum = n+1 // 不加也可以，有人喜欢以0开头
us.father = make([]int, us.nodeNum)
for i, _ := range us.father {
us.father[i] = i
}
}
//合并结点
func (us *UnionFindSet) Union(x, y int) bool {
x = us.FindV2(x)
y = us.FindV2(y)
if x == y {
return false
}
us.father[x] = y
return true
}
func (us *UnionFindSet) FindV2(x int) int {
root := x // 保存好路径上的头结点
for us.father[root] != root {
root = us.father[root]
}
/*
从头结点开始一直往根上遍历
把所有结点的father直接指向root。
*/
for us.father[x] != x {
// 一定要先保存好下一个结点，下一步是要对us.father[x]进行赋值
temp := us.father[x]
us.father[x] = root
x = temp
}
return root
}
func getSameNum(source []int, target []int, set []int) int {
cnt := make(map[int]int)
for _, v := range set {
cnt[source[v]]++
}
sum :=0
for _, v := range set {
if cnt[target[v]]>0{
sum++
cnt[target[v]]--
}
}
return sum
}
func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int {
us := UnionFindSet{}
us.InitUnionSet(len(target)+2)
for _, v := range allowedSwaps{
us.Union(v[0], v[1])
}
set := make([][]int, len(target)) // 保存以为个结点为根的集合，不一定都有元素
for i:=0;i<len(target);i++ {
f := us.FindV2(i)
if set[f] == nil {set[f] = []int{}}
set[f] = append(set[f], i)
}
sum :=0
for _, s := range set {
sum += getSameNum(source, target, s)
}
return len(target)-sum
}
相关题目
并查集学习资料 这里都总结好了