minimize-hamming-distance-after-swap-operations

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two integer arrays, <code>source</code> and <code>target</code>, both of length <code>n</code>. You are also given an array <code>allowedSwaps</code> where each <code>allowedSwaps[i] = [ai, bi]</code> indicates that you are allowed to swap the elements at index <code>ai</code> and index <code>bi</code> (0-indexed) of array <code>source</code>. Note that you can swap elements at a specific pair of indices multiple times and in any order.

The Hamming distance of two arrays of the same length, <code>source</code> and <code>target</code>, is the number of positions where the elements are different. Formally, it is the number of indices <code>i</code> for <code>0 &lt;= i &lt;= n-1</code> where <code>source[i] != target[i]</code> (0-indexed).

Return the minimum Hamming distance of <code>source</code> and <code>target</code> after performing any amount of swap operations on array <code>source</code>.

&nbsp;
Example 1:

<pre>
Input: source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
Output: 1
Explanation: source can be transformed the following way:
- Swap indices 0 and 1: source = [2,1,3,4]
- Swap indices 2 and 3: source = [2,1,4,3]
The Hamming distance of source and target is 1 as they differ in 1 position: index 3.
</pre>

Example 2:

<pre>
Input: source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
Output: 2
Explanation: There are no allowed swaps.
The Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.
</pre>

Example 3:

<pre>
Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
Output: 0
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == source.length == target.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= source[i], target[i] &lt;= 105</code></li>
	<li><code>0 &lt;= allowedSwaps.length &lt;= 105</code></li>
	<li><code>allowedSwaps[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt;= n - 1</code></li>
	<li><code>ai != bi</code></li>
</ul>

minimumHammingDistance

Minimize Hamming Distance After Swap Operations

Smallest String With Swaps

smallest-string-with-swaps

交换字符串中的元素

Make Lexicographically Smallest Array by Swapping Elements

make-lexicographically-smallest-array-by-swapping-elements

交换得到字典序最小的数组

Depth-First Search

Union Find

Array

给你两个整数数组 <code>source</code> 和 <code>target</code> ，长度都是 <code>n</code> 。还有一个数组 <code>allowedSwaps</code> ，其中每个 <code>allowedSwaps[i] = [ai, bi]</code> 表示你可以交换数组 <code>source</code> 中下标为 <code>ai</code> 和 <code>bi</code>（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。

相同长度的两个数组 <code>source</code> 和 <code>target</code> 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 <code>source[i] != target[i]</code> （下标从 0 开始）的下标 <code>i</code>（<code>0 &lt;= i &lt;= n-1</code>）的数量。

在对数组 <code>source</code> 执行 任意 数量的交换操作后，返回 <code>source</code> 和 <code>target</code> 间的 最小汉明距离 。

 

示例 1：

<pre>输入：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 。
</pre>

示例 2：

<pre>输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。</pre>

示例 3：

<pre>输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0
</pre>

 

提示：

<ul>
	<li><code>n == source.length == target.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= source[i], target[i] &lt;= 105</code></li>
	<li><code>0 &lt;= allowedSwaps.length &lt;= 105</code></li>
	<li><code>allowedSwaps[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt;= n - 1</code></li>
	<li><code>ai != bi</code></li>
</ul>