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

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

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

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) { } };

php 解法, 执行用时: 464 ms, 内存消耗: 111.9 MB, 提交时间: 2023-06-06 10:14:12

class UnionSet
{
    private $rank;
    private $parent;
    /**
     * @param int $n
     * @return null
     */
    function __construct($n)
    {
        $this->$n = $n;
        $this->rank = array_fill(0, $n, 1);
        for ($i = 0; $i < $n; ++$i) {
            $this->parent[$i] = $i;
        }
    }
    /**
     * @param int $x
     * @return int
     */
    function find($x)
    {
        if ($x != $this->parent[$x]) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }
    /**
     * @param int $x
     * @param int $y
     * @return null
     */
    function union($x, $y)
    {
        $xr = $this->find($x);
        $yr = $this->find($y);
        if ($xr == $yr) return;
        if ($this->rank[$xr] < $this->rank[$yr]) {
            $this->parent[$xr] = $yr;
        } else if ($this->rank[$xr] > $this->rank[$yr]) {
            $this->parent[$yr] = $xr;
        } else {
            $this->parent[$xr] = $yr;
            $this->rank[$yr]++;
        }
    }
}
class Solution {

    /**
     * @param Integer[] $source
     * @param Integer[] $target
     * @param Integer[][] $allowedSwaps
     * @return Integer
     */
    function minimumHammingDistance($source, $target, $allowedSwaps) {
        $n = count($source);
        $dsu = new UnionSet($n);
        foreach ($allowedSwaps as $a) $dsu->union($a[0], $a[1]);
        $map = [];
        for ($i = 0; $i < $n; ++$i) {
            $f = $dsu->find($i);
            $s = $source[$i];
            $map[$f][$s] = isset($map[$f][$s]) ? $map[$f][$s] + 1 : 1;
        }
        $same = 0;
        for ($i = 0; $i < $n; ++$i) {
            $f = $dsu->find($i);
            $t = $target[$i];
            if (isset($map[$f][$t]) && $map[$f][$t] > 0) {
                $same++;
                $map[$f][$t]--;
            }
        }
        return $n - $same;
    }
}

python3 解法, 执行用时: 544 ms, 内存消耗: 68.5 MB, 提交时间: 2023-06-06 10:13:50

# dfs, 用DFS分组，组内每个位置都可以互换，所以hamming distance就是个数的差别。
class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]):
        n = len(source)
        graph = collections.defaultdict(list)
        for i, j in allowedSwaps:
            graph[i].append(j)
            graph[j].append(i)
        group, cnt = [0]*n, 0
        for i in range(n):
            if group[i] == 0:
                cnt +=1
                group[i], s = cnt, [i]
                while s:
                    cur = s.pop()
                    for j in graph[cur]:
                        if group[j] == 0:
                            group[j] = cnt
                            s.append(j)
        s = [[] for _ in range(cnt+1)]
        t = [[] for _ in range(cnt+1)]
        for i in range(n):
            s[group[i]].append(source[i])
            t[group[i]].append(target[i])
        res = 0
        for i in range(cnt+1):
            dic_s = collections.Counter(s[i])
            dic_t = collections.Counter(t[i])
            for d in dic_s:
                res += max(0, dic_s[d] - dic_t[d])
        return res

python3 解法, 执行用时: 748 ms, 内存消耗: 65.3 MB, 提交时间: 2023-06-06 10:11:50

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n=len(source)
        parent={i:i for i in range(n)}
        # 并查集
        def find(x):
            if x!=parent[x]:
                parent[x]=find(parent[x])
            return parent[x]
        # 搜索根节点
        for l,r in allowedSwaps:
            a,b=find(l),find(r)
            if a!=b:
                parent[b]=a
        # 获取根节点对应的连通块
        dic=collections.defaultdict(list)
        for i in range(n):
            a=find(i)
            dic[a].append(i)
        # 计算每个连通块对应的source元素与target的差集
        count=0
        for k,v in dic.items():
            a=Counter([source[i] for i in v])
            b=Counter([target[i] for i in v])
            count+=len(list((a&b).elements()))
        return n-count

python3 解法, 执行用时: 524 ms, 内存消耗: 63.1 MB, 提交时间: 2023-06-06 10:11:33

class Solution:
    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:
        n=len(source)
        parent={i:i for i in range(n)}
        # 并查集
        def find(x):
            if x!=parent[x]:
                parent[x]=find(parent[x])
            return parent[x]
        # 搜索根节点
        for l,r in allowedSwaps:
            a,b=find(l),find(r)
            if a!=b:
                parent[b]=a
        # 获取根节点对应的连通块
        dic=collections.defaultdict(list)
        for i in range(n):
            a=find(i)
            dic[a].append(i)
        res=0
        # 计算每个连通块对应的source元素与target的差集
        for k,v in dic.items():
            a=[source[i] for i in v]
            b=Counter([target[i] for i in v])
            for c in a:
                if b[c]>0:
                    b[c]-=1
                else:
                    res+=1
        return res

golang 解法, 执行用时: 224 ms, 内存消耗: 20.8 MB, 提交时间: 2023-06-06 10:10:36

// 使用并查集

// 返回根节点
func find(x int, parent []int) int {
	if parent[x] != x { // 判断如果不是根节点
		parent[x] = find(parent[x], parent) // 顺便进行路径压缩，即将父节点指向根节点
	}
	return parent[x]
}
func minimumHammingDistance(source []int, target []int, allowedSwaps [][]int) int {
	parent := make([]int, len(source)) // 记录每个idx的父节点
	// 初始化为自己
	for i := 0; i < len(source); i++ {
		parent[i] = i
	}
	for _, pair := range allowedSwaps {
		root_a, root_b := find(pair[0], parent), find(pair[1], parent)
		parent[root_a] = root_b // 联合两棵树
	}
	// 找出所有的树
	trees := make(map[int][]int, 0)
	for i := 0; i < len(source); i++ {
		j := find(i, parent)
		if _, ok := trees[j]; !ok {
			trees[j] = make([]int, 0)
		}
		trees[j] = append(trees[j], i)
	}
	// 在每棵树上，计算最小汉明距离
	ans := 0
	for _, set := range trees {
		// 同一棵树内的idx可以任意互换位置，所以只需要考虑数字的计数
		countTarget := make(map[int]int, 0)
		for _, idx := range set {
			if countTarget[target[idx]] == 0 {
				countTarget[target[idx]] = 1
			} else {
				countTarget[target[idx]]++
			}
		}
		for _, idx := range set {
			if countTarget[source[idx]] == 0 {
				ans++
			} else {
				countTarget[source[idx]]--
			}
		}
	}
	return ans
}

上一题

下一题

详情