{"id":8780,"date":"2021-11-26T12:32:13","date_gmt":"2021-11-26T20:32:13","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8780"},"modified":"2021-11-26T13:06:35","modified_gmt":"2021-11-26T21:06:35","slug":"leetcode-2009-minimum-number-of-operations-to-make-array-continuous","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sliding-window\/leetcode-2009-minimum-number-of-operations-to-make-array-continuous\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2009. Minimum Number of Operations to Make Array Continuous"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>nums<\/code>. In one operation, you can replace&nbsp;<strong>any<\/strong>&nbsp;element in&nbsp;<code>nums<\/code>&nbsp;with&nbsp;<strong>any<\/strong>&nbsp;integer.<\/p>\n\n\n\n<p><code>nums<\/code>&nbsp;is considered&nbsp;<strong>continuous<\/strong>&nbsp;if both of the following conditions are fulfilled:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>All elements in&nbsp;<code>nums<\/code>&nbsp;are&nbsp;<strong>unique<\/strong>.<\/li><li>The difference between the&nbsp;<strong>maximum<\/strong>&nbsp;element and the&nbsp;<strong>minimum<\/strong>&nbsp;element in&nbsp;<code>nums<\/code>&nbsp;equals&nbsp;<code>nums.length - 1<\/code>.<\/li><\/ul>\n\n\n\n<p>For example,&nbsp;<code>nums = [4, 2, 5, 3]<\/code>&nbsp;is&nbsp;<strong>continuous<\/strong>, but&nbsp;<code>nums = [1, 2, 3, 5, 6]<\/code>&nbsp;is&nbsp;<strong>not continuous<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of operations to make&nbsp;<\/em><code>nums<\/code><strong><em>continuous<\/em><\/strong>.<\/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 = [4,2,5,3]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong>&nbsp;nums is already continuous.\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 = [1,2,3,5,6]\n<strong>Output:<\/strong> 1\n<strong>Explanation:<\/strong>&nbsp;One possible solution is to change the last element to 4.\nThe resulting array is [1,2,3,5,4], which is continuous.\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 = [1,10,100,1000]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong>&nbsp;One possible solution is to:\n- Change the second element to 2.\n- Change the third element to 3.\n- Change the fourth element to 4.\nThe resulting array is [1,2,3,4], which is continuous.\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;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= nums[i] &lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Sliding Window<\/strong><\/h2>\n\n\n\n<p>Remove duplicates and sort the numbers.<br>Try using nums[i] as the min number of the final array.<br>window [i, j), max &#8211; min &lt; n, then change the rest of array to fit into or append after the window, which takes n &#8211; (j &#8211; i) steps.<br>e.g. input = [10, 3, 1, 4, 5, 6, 6, 6, 11, 15] => sorted + unique => [1, 3, 4, 5, 6, 10, 11, 15]<br>n = 10, window = [3, 4, 5, 6, 10, 11], max = 11, min = 3, max &#8211; min = 8 &lt; 10<br>Final array = [3, 4, 5, 6, <strong><span class=\"has-inline-color has-vivid-red-color\">1->7, 6<sub>2<\/sub>->8, 6<sub>3<\/sub>->9<\/span><\/strong>, 10, 11, <strong><span class=\"has-inline-color has-vivid-red-color\">15->12<\/span><\/strong>] <br>Time complexity: O(n)<br>Space complexity: O(1)<\/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 minOperations(vector<int>& A) {\n    const int n = A.size();\n    sort(begin(A), end(A));\n    A.erase(unique(begin(A), end(A)), end(A));    \n    int ans = INT_MAX;\n    for (int i = 0, j = 0, m = A.size(); i < m; ++i) {\n      while (j < m &#038;&#038; A[j] < A[i] + n) ++j;\n      ans = min(ans, n - (j - i));\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;nums. In one operation, you can replace&nbsp;any&nbsp;element in&nbsp;nums&nbsp;with&nbsp;any&nbsp;integer. nums&nbsp;is considered&nbsp;continuous&nbsp;if both of the following conditions are fulfilled: All elements in&nbsp;nums&nbsp;are&nbsp;unique.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[476],"tags":[217,215,41,240],"class_list":["post-8780","post","type-post","status-publish","format-standard","hentry","category-sliding-window","tag-hard","tag-sliding-window","tag-subarray","tag-unique","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8780","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=8780"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8780\/revisions"}],"predecessor-version":[{"id":8784,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8780\/revisions\/8784"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}