1722 - 执行交换操作后的最小汉明距离 - 并查集 - 哈希 -贪心 - DFS

题目描述

[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

Related Topics
  • 并查集
  • 图连通块
  • DFS
  • 题目剖析&信息挖掘

    题目考查的是图连通块的查找,可以使用并查集或者深度优先遍历实现。并查集更加简便,我使用的是并查集。

    并查集还不会?赶紧来学习吧并查集学习资料

    解题思路

    方法一 并查集+哈希+贪心

    分析

    首先,可以发现一个规律。

    交换关系具有传递性。即如果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
    }
    

    相关题目

    并查集学习资料 这里都总结好了

    1赞