{"id":9383,"date":"2021-12-31T22:49:23","date_gmt":"2022-01-01T06:49:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9383"},"modified":"2021-12-31T22:55:45","modified_gmt":"2022-01-01T06:55:45","slug":"leetcode-1998-gcd-sort-of-an-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1998-gcd-sort-of-an-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1998. GCD Sort of an Array"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>nums<\/code>, and you can perform the following operation&nbsp;<strong>any<\/strong>&nbsp;number of times on&nbsp;<code>nums<\/code>:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Swap the positions of two elements&nbsp;<code>nums[i]<\/code>&nbsp;and&nbsp;<code>nums[j]<\/code>&nbsp;if&nbsp;<code>gcd(nums[i], nums[j]) &gt; 1<\/code>&nbsp;where&nbsp;<code>gcd(nums[i], nums[j])<\/code>&nbsp;is the&nbsp;<strong>greatest common divisor<\/strong>&nbsp;of&nbsp;<code>nums[i]<\/code>&nbsp;and&nbsp;<code>nums[j]<\/code>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<code>true<\/code>&nbsp;<em>if it is possible to sort&nbsp;<\/em><code>nums<\/code><em>&nbsp;in&nbsp;<strong>non-decreasing<\/strong>&nbsp;order using the above swap method, or&nbsp;<\/em><code>false<\/code><em>&nbsp;otherwise.<\/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> nums = [7,21,3]\n<strong>Output:<\/strong> true\n<strong>Explanation:<\/strong> We can sort [7,21,3] by performing the following operations:\n- Swap 7 and 21 because gcd(7,21) = 7. nums = [<strong>21<\/strong>,<strong>7<\/strong>,3]\n- Swap 21 and 3 because gcd(21,3) = 3. nums = [<strong>3<\/strong>,7,<strong>21<\/strong>]\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> nums = [5,2,6,2]\n<strong>Output:<\/strong> false\n<strong>Explanation:<\/strong> It is impossible to sort the array because 5 cannot be swapped with any other element.\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> nums = [10,5,9,3,15]\n<strong>Output:<\/strong> true\nWe can sort [10,5,9,3,15] by performing the following operations:\n- Swap 10 and 15 because gcd(10,15) = 5. nums = [<strong>15<\/strong>,5,9,3,<strong>10<\/strong>]\n- Swap 15 and 3 because gcd(15,3) = 3. nums = [<strong>3<\/strong>,5,9,<strong>15<\/strong>,10]\n- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,<strong>10<\/strong>,<strong>15<\/strong>]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4<\/sup><\/code><\/li><li><code>2 &lt;= nums[i] &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Union-Find<\/strong><\/h2>\n\n\n\n<p>Let nums[j]&#8217;s target position be i. In order to put nums[j] to pos i by swapping. nums[i] and nums[j] must be in the same connected component. There is an edge between two numbers if they have gcd > 1.<\/p>\n\n\n\n<p>We union two numbers if their have gcd > 1. However, it will be TLE if we do all pairs . Thus, for each number, we union it with its divisors instead.<\/p>\n\n\n\n<p>Time complexity: O(n<sup>2<\/sup>) TLE -> O(sum(sqrt(nums[i]))) &lt;= O(n*sqrt(m))<br>Space complexity: O(n)<\/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  bool gcdSort(vector<int>& nums) {\n    const int m = *max_element(begin(nums), end(nums));\n    const int n = nums.size();\n    \n    vector<int> p(m + 1);\n    iota(begin(p), end(p), 0);\n  \n    function<int(int)> find = [&](int x) {\n      return p[x] == x ? x : (p[x] = find(p[x]));\n    };\n  \n    for (int x : nums)\n      for (int d = 2; d <= sqrt(x); ++d)\n        if (x % d == 0)\n          p[find(x)] = p[find(x \/ d)] = find(d);\n\n    vector<int> sorted(nums);\n    sort(begin(sorted), end(sorted));\n    \n    for (int i = 0; i < n; ++i)\n      if (find(sorted[i]) != find(nums[i])) \n        return false;\n\n    return true;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;nums, and you can perform the following operation&nbsp;any&nbsp;number of times on&nbsp;nums: Swap the positions of two elements&nbsp;nums[i]&nbsp;and&nbsp;nums[j]&nbsp;if&nbsp;gcd(nums[i], nums[j]) &gt; 1&nbsp;where&nbsp;gcd(nums[i],&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[359,77,217,31,59,61,113],"class_list":["post-9383","post","type-post","status-publish","format-standard","hentry","category-graph","tag-gcd","tag-graph","tag-hard","tag-math","tag-prime","tag-sqrt","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9383","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=9383"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9383\/revisions"}],"predecessor-version":[{"id":9386,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9383\/revisions\/9386"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}