文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你兩個整數(shù)數(shù)組 source 和 target ，長度都是 n 。
還有一個數(shù)組 allowedSwaps ，其中每個 allowedSwaps[i] = [ai, bi] 表示你可以交換數(shù)組 source 中下標為 ai 和 bi（下標從 0 開始）的兩個元素。
注意，你可以按 任意 順序 多次 交換一對特定下標指向的元素。

相同長度的兩個數(shù)組 source 和 target 間的 漢明距離 是元素不同的下標數(shù)量。
形式上，其值等于滿足 source[i] != target[i] （下標從 0 開始）的下標 i（0 <= i <= n-1）的數(shù)量。

在對數(shù)組 source 執(zhí)行 任意 數(shù)量的交換操作后，返回 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 執(zhí)行交換操作。 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

https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/

2. 解題

并查集學習，請點擊

• 對可以交換的下標位置，使用并查集進行合并
• 對 source 數(shù)組中每個位置的數(shù)，屬于哪個集合，計數(shù)
• 遍歷 target 數(shù)組，對每個位置的數(shù)，查看對應集合，看是否存在，記錄數(shù)量，并更新計數(shù)

class dsu // 并查集 { public:vector<int> f;dsu(int n){f.resize(n);for(int i = 0; i < n; i++)f[i] = i;}void merge(int a, int b){int fa = find(a);int fb = find(b);f[fa] = fb;}int find(int a){if(a == f[a])return a;return f[a] = find(f[a]);} }; class Solution { public:int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {int n = source.size();dsu u(n);for(auto& a : allowedSwaps)u.merge(a[0], a[1]);int same = 0;unordered_map<int,unordered_map<int,int>> m;for(int i = 0; i < n; i++){int fa = u.find(i);m[fa][source[i]]++;}for(int i = 0; i < n; i++){int fa = u.find(i);if(m[fa][target[i]] > 0){same++;m[fa][target[i]]--;}}return n-same;} };

908 ms 145.2 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1722. 执行交换操作后的最小汉明距离（并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。