{"id":3044,"date":"2018-07-09T08:31:50","date_gmt":"2018-07-09T15:31:50","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3044"},"modified":"2018-07-12T06:47:13","modified_gmt":"2018-07-12T13:47:13","slug":"leetcode-775-global-and-local-inversions","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/divide-and-conquer\/leetcode-775-global-and-local-inversions\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 775. Global and Local Inversions"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 775. Global and Local Inversions - \u5237\u9898\u627e\u5de5\u4f5c EP206\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/3QHSJSFm0W0?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>Problem<\/h1>\n<p>We have some permutation\u00a0<code>A<\/code>\u00a0of\u00a0<code>[0, 1, ..., N - 1]<\/code>, where\u00a0<code>N<\/code>\u00a0is the length of\u00a0<code>A<\/code>.<\/p>\n<p>The number of (global) inversions is the number of\u00a0<code>i &lt; j<\/code>\u00a0with\u00a0<code>0 &lt;= i &lt; j &lt; N<\/code>\u00a0and\u00a0<code>A[i] &gt; A[j]<\/code>.<\/p>\n<p>The number of local inversions is the number of\u00a0<code>i<\/code>\u00a0with\u00a0<code>0 &lt;= i &lt; N<\/code>\u00a0and\u00a0<code>A[i] &gt; A[i+1]<\/code>.<\/p>\n<p>Return\u00a0<code>true<\/code>\u00a0if and only if the number of global inversions is equal to the number of local inversions.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input:<\/strong> A = [1,0,2]\r\n<strong>Output:<\/strong> true\r\n<strong>Explanation:<\/strong> There is 1 global inversion, and 1 local inversion.\r\n<\/pre>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false \"><strong>Input:<\/strong> A = [1,2,0]\r\n<strong>Output:<\/strong> false\r\n<strong>Explanation:<\/strong> There are 2 global inversions, and 1 local inversion.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>A<\/code>\u00a0will be a permutation of\u00a0<code>[0, 1, ..., A.length - 1]<\/code>.<\/li>\n<li><code>A<\/code>\u00a0will have length in range\u00a0<code>[1, 5000]<\/code>.<\/li>\n<li>The time limit for this problem has been reduced.<\/li>\n<\/ul>\n<h1>Solution1: Brute Force (TLE)<\/h1>\n<p>Time complexity: O(n^2)<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: TLE (208\/208 test cases passed)\r\nclass Solution {\r\npublic:\r\n  bool isIdealPermutation(vector&lt;int&gt;&amp; A) {\r\n    const int n = A.size();\r\n    int local = 0;\r\n    for (int i = 0; i &lt; n - 1; ++i)\r\n      if (A[i] &gt; A[i + 1]) ++local;\r\n    int global = 0;\r\n    for (int i = 0; i &lt; n; ++i)\r\n      for (int j = i + 1; j &lt; n; ++j)\r\n        if (A[i] &gt; A[j] &amp;&amp; ++global &gt; local) return false;\r\n    return global == local;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<h1>Solution2: MergeSort<\/h1>\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 52 ms (&lt;96.42%)\r\nclass Solution {\r\npublic:\r\n  bool isIdealPermutation(vector&lt;int&gt;&amp; A) {\r\n    const int n = A.size();\r\n    int local = 0;\r\n    for (int i = 0; i &lt; n - 1; ++i)\r\n      if (A[i] &gt; A[i + 1]) ++local;\r\n    tmp = vector&lt;int&gt;(n);\r\n    int global = mergeSort(A, 0, n - 1);\r\n    return global == local;\r\n  }\r\nprivate:\r\n  vector&lt;int&gt; tmp;\r\n  int mergeSort(vector&lt;int&gt;&amp; A, int l, int r) {\r\n    if (l &gt;= r) return 0;\r\n    const int len = r - l + 1;\r\n    int m = (r - l) \/ 2 + l;\r\n    int inv = mergeSort(A, l, m) + mergeSort(A, m + 1, r);\r\n        \r\n    int i = l;\r\n    int j = m + 1;\r\n    int k = 0;\r\n    \r\n    while (i &lt;= m &amp;&amp; j &lt;= r) {\r\n      if (A[i] &lt;= A[j]) {\r\n        tmp[k++] = A[i++];\r\n      } else {\r\n        tmp[k++] = A[j++];\r\n        inv += m - i + 1;\r\n      }\r\n    }\r\n    \r\n    while (i &lt;= m) tmp[k++] = A[i++];\r\n    while (j &lt;= r) tmp[k++] = A[j++];\r\n    \r\n    std::copy(tmp.begin(), tmp.begin() + len, A.begin() + l);\r\n    \r\n    return inv;\r\n  }\r\n};<\/pre>\n<p>C#<\/p>\n<pre class=\"lang:c# decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 208 ms\r\npublic class Solution {\r\n  public bool IsIdealPermutation(int[] A) {\r\n    var n = A.Length;\r\n    var localInv = 0;\r\n    for (var i = 1; i &lt; n; ++i)\r\n      if (A[i] &lt; A[i - 1]) ++localInv;\r\n    tmp = new int[n];\r\n    var globalInv = MergeSort(A, 0, n - 1);    \r\n    return localInv == globalInv;\r\n  }  \r\n  private int[] tmp;  \r\n  private int MergeSort(int[] A, int l, int r) {\r\n    if (l &gt;= r) return 0;\r\n    int m = (r - l) \/ 2 + l;\r\n    int inv = MergeSort(A, l, m) + MergeSort(A, m + 1, r);\r\n    int i = l;\r\n    int j = m + 1;\r\n    int k = 0;\r\n    \r\n    while (i &lt;= m &amp;&amp; j &lt;= r) {\r\n      if (A[i] &lt;= A[j]) {\r\n        tmp[k++] = A[i++];\r\n      } else {\r\n        inv += m - i + 1;\r\n        tmp[k++] = A[j++];\r\n      }\r\n    }\r\n    \r\n    while (i &lt;= m) tmp[k++] = A[i++];\r\n    while (j &lt;= r) tmp[k++] = A[j++];\r\n    \r\n    Array.Copy(tmp, 0, A, l, k);\r\n    \r\n    return inv;\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<h1>Solution3: Input Property<\/h1>\n<p>Input is a permutation of [0, 1, &#8230;, N &#8211; 1]<\/p>\n<p>Time Complexity: O(n)<\/p>\n<p>Space Complexity: O(1)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 40 ms (&lt;99.26%)\r\nclass Solution {\r\npublic:\r\n  bool isIdealPermutation(vector&lt;int&gt;&amp; A) {\r\n    for (int i = 0; i &lt; A.size(); ++i)\r\n        if (abs(A[i] - i) &gt; 1) return false;\r\n\t  return true;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem We have some permutation\u00a0A\u00a0of\u00a0[0, 1, &#8230;, N &#8211; 1], where\u00a0N\u00a0is the length of\u00a0A. The number of (global) inversions is the number of\u00a0i &lt; j\u00a0with\u00a00&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,43],"tags":[313,320,177,321],"class_list":["post-3044","post","type-post","status-publish","format-standard","hentry","category-array","category-divide-and-conquer","tag-divide-and-conquer","tag-inversion","tag-medium","tag-mergesort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3044","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=3044"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3044\/revisions"}],"predecessor-version":[{"id":3085,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3044\/revisions\/3085"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3044"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3044"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3044"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}