题目描述
给定两个整数数组 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
间的 最小汉明距离。
样例
输入:
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。
输入:
source = [1,2,3,4]
target = [1,3,2,4]
allowedSwaps = []
输出:2
解释:不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2,二者有 2 处元素不同,在下标 1 和下标 2。
输入:
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 <= a_i, b_i <= n - 1
a_i != b_i
算法
(并查集,哈希表) $O(n)$
- 将下标
0
到n - 1
按照allowedSwaps
进行分组,[x, y]
表示下标x
和下标y
在同一组。由于可以任意多次操作,所以在同一组内的下标之间可以任意交换值。 - 通过并查集可以计算出分组。
- 对于每个组,通过哈希表求出
source
与target
的不同值的差距。
时间复杂度
- 假设并查集
find
的时间为常数,则分组的时间为 $O(n)$。 - 分组后,通过哈希表计算差距的总时间也为 $O(n)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储并查集数据结构和哈希表。
C++ 代码
class Solution {
private:
vector<int> f, sz;
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (sz[fx] < sz[fy]) {
f[fx] = fy;
sz[fy] += sz[fx];
} else {
f[fy] = fx;
sz[fx] += sz[fy];
}
}
}
public:
int minimumHammingDistance(vector<int>& source, vector<int>& target,
vector<vector<int>>& allowedSwaps) {
const int n = source.size();
f.resize(n);
sz.resize(n, 1);
for (int i = 0; i < n; i++)
f[i] = i;
for (const auto &e : allowedSwaps)
merge(e[0], e[1]);
vector<vector<int>> mp(n);
for (int i = 0; i < n; i++)
mp[find(i)].push_back(i);
int ans = 0;
for (int i = 0; i < n; i++) {
unordered_map<int, int> seen;
for (int j : mp[i]) {
seen[source[j]]++;
seen[target[j]]--;
}
for (const auto &it : seen)
ans += abs(it.second);
}
return ans / 2;
}
};