{"id":7967,"date":"2021-01-10T10:30:19","date_gmt":"2021-01-10T18:30:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7967"},"modified":"2021-01-10T10:36:34","modified_gmt":"2021-01-10T18:36:34","slug":"leetcode-1722-minimize-hamming-distance-after-swap-operations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/uncategorized\/leetcode-1722-minimize-hamming-distance-after-swap-operations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1722. Minimize Hamming Distance After Swap Operations"},"content":{"rendered":"\n<p>You are given two integer arrays,&nbsp;<code>source<\/code>&nbsp;and&nbsp;<code>target<\/code>, both of length&nbsp;<code>n<\/code>. You are also given an array&nbsp;<code>allowedSwaps<\/code>&nbsp;where each&nbsp;<code>allowedSwaps[i] = [a<sub>i<\/sub>, b<sub>i<\/sub>]<\/code>&nbsp;indicates that you are allowed to swap the elements at index&nbsp;<code>a<sub>i<\/sub><\/code>&nbsp;and index&nbsp;<code>b<sub>i<\/sub><\/code>&nbsp;<strong>(0-indexed)<\/strong>&nbsp;of array&nbsp;<code>source<\/code>. Note that you can swap elements at a specific pair of indices&nbsp;<strong>multiple<\/strong>&nbsp;times and in&nbsp;<strong>any<\/strong>&nbsp;order.<\/p>\n\n\n\n<p>The&nbsp;<strong>Hamming distance<\/strong>&nbsp;of two arrays of the same length,&nbsp;<code>source<\/code>&nbsp;and&nbsp;<code>target<\/code>, is the number of positions where the elements are different. Formally, it is the number of indices&nbsp;<code>i<\/code>&nbsp;for&nbsp;<code>0 &lt;= i &lt;= n-1<\/code>&nbsp;where&nbsp;<code>source[i] != target[i]<\/code>&nbsp;<strong>(0-indexed)<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum Hamming distance<\/strong>&nbsp;of&nbsp;<\/em><code>source<\/code><em>&nbsp;and&nbsp;<\/em><code>target<\/code><em>&nbsp;after performing&nbsp;<strong>any<\/strong>&nbsp;amount of swap operations on array&nbsp;<\/em><code>source<\/code><em>.<\/em><\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong> source can be transformed the following way:\n- Swap indices 0 and 1: source = [2,1,3,4]\n- Swap indices 2 and 3: source = [2,1,4,3]\nThe Hamming distance of source and target is 1 as they differ in 1 position: index 3.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> There are no allowed swaps.\nThe Hamming distance of source and target is 2 as they differ in 2 positions: index 1 and index 2.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == source.length == target.length<\/code><\/li><li><code>1 &lt;= n &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= source[i], target[i] &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= allowedSwaps.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>allowedSwaps[i].length == 2<\/code><\/li><li><code>0 &lt;= a<sub>i<\/sub>, b<sub>i<\/sub>&nbsp;&lt;= n - 1<\/code><\/li><li><code>a<sub>i<\/sub>&nbsp;!= b<sub>i<\/sub><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Union Find<\/strong><\/h2>\n\n\n\n<p>Similar to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1202-smallest-string-with-swaps\/\" data-type=\"post\" data-id=\"5573\">\u82b1\u82b1\u9171 LeetCode 1202. Smallest String With Swaps<\/a><\/p>\n\n\n\n<p>Think each pair as an edge in a graph. Since we can swap as many time as we want, which means we can arrange the elements whose indices are in a connected component (CC) in any order.<\/p>\n\n\n\n<p>For each index i, we increase the counter of CC(i) for key source[i] and decrease the counter of the same CC for key target[i]. If two keys are the same (can from different indices), one from source and one from target, it will cancel out, no distance. Otherwise, the counter will be off by two. Finally we sum up the counter for all the keys and divide it by two to get the hamming distance.<\/p>\n\n\n\n<p>Time complexity: O(V+E)<br>Space complexity: O(V)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: huahua\nclass Solution {\npublic:\n  int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {\n    const int n = source.size();\n    vector<int> p(n);\n    iota(begin(p), end(p), 0);\n    \n    function<int(int)> find = [&](int x) {\n      return x == p[x] ? x : p[x] = find(p[x]);\n    };\n    \n    for (const auto& s : allowedSwaps)\n      p[find(s[0])] = find(s[1]);\n    \n    unordered_map<int, unordered_map<int, int>> m;\n    for (int i = 0; i < n; ++i) {\n      ++m[find(i)][source[i]];\n      --m[find(i)][target[i]];\n    }\n    \n    int ans = 0;\n    for (const auto&#038; g : m) \n      for (const auto&#038; kv : g.second)\n        ans += abs(kv.second);\n    return ans \/ 2;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two integer arrays,&nbsp;source&nbsp;and&nbsp;target, both of length&nbsp;n. You are also given an array&nbsp;allowedSwaps&nbsp;where each&nbsp;allowedSwaps[i] = [ai, bi]&nbsp;indicates that you are allowed to swap&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7967","post","type-post","status-publish","format-standard","hentry","category-uncategorized","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7967","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7967"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7967\/revisions"}],"predecessor-version":[{"id":7974,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7967\/revisions\/7974"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7967"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7967"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7967"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}