1722. Minimize Hamming Distance After Swap Operations
Description
You are given two integer arrays, source
and target
, both of length n
. You are also given an array allowedSwaps
where each allowedSwaps[i] = [ai, bi]
indicates that you are allowed to swap the elements at index ai
and index bi
(0-indexed) of array source
. 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, source
and target
, is the number of positions where the elements are different. Formally, it is the number of indices i
for 0 <= i <= n-1
where source[i] != target[i]
(0-indexed).
Return the minimum Hamming distance of source
and target
after performing any amount of swap operations on array source
.
Example 1:
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.
Example 2:
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.
Example 3:
Input: source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]] Output: 0
Constraints:
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
Solutions
Solution 1: Union-Find + Hash Table
We can consider each index as a node, and the element corresponding to each index as the value of the node. Then each element [a_i, b_i]
in the given allowedSwaps
represents an edge between index a_i
and b_i
. Therefore, we can use a union-find set to maintain these connected components.
After obtaining each connected component, we use a two-dimensional hash table $cnt$ to count the number of occurrences of each element in each connected component. Finally, for each element in the array target
, if its occurrence count in the corresponding connected component is greater than 0, we decrease its count by 1, otherwise, we increase the answer by 1.
The time complexity is $O(n \times \log n)$ or $O(n \times \alpha(n))$, and the space complexity is $O(n)$. Here, $n$ is the length of the array, and $\alpha$ is the inverse Ackermann function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|