{"id":6226,"date":"2020-02-01T09:49:53","date_gmt":"2020-02-01T17:49:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6226"},"modified":"2020-02-06T21:10:52","modified_gmt":"2020-02-07T05:10:52","slug":"leetcode-912-sort-an-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-912-sort-an-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 912. Sort an Array"},"content":{"rendered":"\n<p>Given an array of integers&nbsp;<code>nums<\/code>, sort the array in ascending order.<\/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 = [5,2,3,1]\n<strong>Output:<\/strong> [1,2,3,5]\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,1,1,2,0,0]\n<strong>Output:<\/strong> [0,0,1,1,2,5]\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;= 50000<\/code><\/li><li><code>-50000 &lt;= nums[i] &lt;= 50000<\/code><\/li><\/ul>\n\n\n\n<p>Since n &lt;= 50000, any O(n^2) won&#8217;t pass, we need O(nlogn) or better<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: QuickSort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn) ~ O(n^2)<br>Space complexity: O(logn) ~ 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, 60 ms\nclass Solution {\npublic:\n  vector<int> sortArray(vector<int>& nums) {\n    function<void(int, int)> quickSort = [&](int l, int r) {\n      if (l >= r) return;      \n      int i = l;\n      int j = r;\n      int p = nums[l + rand() % (r - l + 1)];\n      while (i <= j) {\n        while (nums[i] < p) ++i;\n        while (nums[j] > p) --j;\n        if (i <= j)\n          swap(nums[i++], nums[j--]);\n      }\n      quickSort(l, j);\n      quickSort(i, r);\n    };\n    quickSort(0, nums.size() - 1);\n    return nums;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Counting Sort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(max(nums) - min(nums))<\/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, 54 ms\nclass Solution {\npublic:\n  vector<int> sortArray(vector<int>& nums) {\n    auto [min_it, max_it] = minmax_element(begin(nums), end(nums));\n    int l = *min_it, r = *max_it;\n    vector<int> count(r - l + 1);\n    for (int n : nums) ++count[n - l];\n    int index = 0;\n    for (int i = 0; i < count.size(); ++i)\n      while (count[i]--) nums[index++] = i + l;\n    return nums;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: HeapSort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<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, 72ms\nclass Solution {\npublic:\n  vector<int> sortArray(vector<int>& nums) {\n    priority_queue<int> q(begin(nums), end(nums));\n    int i = nums.size();\n    while (!q.empty()) {\n      nums[--i] = q.top();\n      q.pop();\n    }\n    return nums;\n  }\n};\n<\/pre>\n<\/div><\/div>\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  vector<int> sortArray(vector<int>& nums) {\n    auto heapify = [&](int i, int e) {\n      while (i <= e) {\n        int l = 2 * i + 1;\n        int r = 2 * i + 2;\n        int j = i;\n        if (l <= e &#038;&#038; nums[l] > nums[j]) j = l;\n        if (r <= e &#038;&#038; nums[r] > nums[j]) j = r;\n        if (j == i) break;\n        swap(nums[i], nums[j]);\n        swap(i, j);\n      }\n    };\n    \n    const int n = nums.size();\n    \n    \/\/ Init heap\n    for (int i = n \/ 2; i >= 0; i--)\n      heapify(i, n - 1);\n    \n    \/\/ Get min.\n    for (int i = n - 1; i >= 1; i--) {\n      swap(nums[0], nums[i]);\n      heapify(0, i - 1);    \n    }\n    \n    return nums;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 3: MergeSort<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(nlogn)<br>Space complexity: O(logn + 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  vector<int> sortArray(vector<int>& nums) {\n    vector<int> t(nums.size());\n    function<void(int, int)> mergeSort = [&](int l, int r) {\n      if (l + 1 >= r) return;\n      int m = l + (r - l) \/ 2;\n      mergeSort(l, m);\n      mergeSort(m, r);\n      int i1 = l;\n      int i2 = m;\n      int index = 0;\n      while (i1 < m || i2 < r)\n        if (i2 == r || (i1 < m &#038;&#038; nums[i1] < nums[i2]))\n          t[index++] = nums[i1++];\n        else\n          t[index++] = nums[i2++];      \n      std::copy(begin(t), begin(t) + index, begin(nums) + l);\n    };\n    \n    mergeSort(0, nums.size());\n    return nums;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 4: BST<\/strong><\/h2>\n\n\n\n<p>Time complexity: (nlogn)<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  vector<int> sortArray(vector<int>& nums) {\n    multiset<int> s(begin(nums), end(nums));\n    return {begin(s), end(s)};\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of integers&nbsp;nums, sort the array in ascending order. Example 1: Input: nums = [5,2,3,1] Output: [1,2,3,5] Example 2: Input: nums = [5,1,1,2,0,0]&#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],"tags":[544,177,376,377,543,15],"class_list":["post-6226","post","type-post","status-publish","format-standard","hentry","category-array","tag-heapsort","tag-medium","tag-on","tag-onlogn","tag-quicksort","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6226","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=6226"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6226\/revisions"}],"predecessor-version":[{"id":6265,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6226\/revisions\/6265"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6226"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6226"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6226"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}