Given an array of integers 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] Output: [0,0,1,1,2,5]
Constraints:
1 <= nums.length <= 50000-50000 <= nums[i] <= 50000
Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better
Solution 1: QuickSort
Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua, 60 ms class Solution { public: vector<int> sortArray(vector<int>& nums) { function<void(int, int)> quickSort = [&](int l, int r) { if (l >= r) return; int i = l; int j = r; int p = nums[l + rand() % (r - l + 1)]; while (i <= j) { while (nums[i] < p) ++i; while (nums[j] > p) --j; if (i <= j) swap(nums[i++], nums[j--]); } quickSort(l, j); quickSort(i, r); }; quickSort(0, nums.size() - 1); return nums; } }; |
Solution 2: Counting Sort
Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 54 ms class Solution { public: vector<int> sortArray(vector<int>& nums) { auto [min_it, max_it] = minmax_element(begin(nums), end(nums)); int l = *min_it, r = *max_it; vector<int> count(r - l + 1); for (int n : nums) ++count[n - l]; int index = 0; for (int i = 0; i < count.size(); ++i) while (count[i]--) nums[index++] = i + l; return nums; } }; |
Solution 2: HeapSort
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua, 72ms class Solution { public: vector<int> sortArray(vector<int>& nums) { priority_queue<int> q(begin(nums), end(nums)); int i = nums.size(); while (!q.empty()) { nums[--i] = q.top(); q.pop(); } return nums; } }; |
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua class Solution { public: vector<int> sortArray(vector<int>& nums) { auto heapify = [&](int i, int e) { while (i <= e) { int l = 2 * i + 1; int r = 2 * i + 2; int j = i; if (l <= e && nums[l] > nums[j]) j = l; if (r <= e && nums[r] > nums[j]) j = r; if (j == i) break; swap(nums[i], nums[j]); swap(i, j); } }; const int n = nums.size(); // Init heap for (int i = n / 2; i >= 0; i--) heapify(i, n - 1); // Get min. for (int i = n - 1; i >= 1; i--) { swap(nums[0], nums[i]); heapify(0, i - 1); } return nums; } }; |
Solution 3: MergeSort
Time complexity: O(nlogn)
Space complexity: O(logn + n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: vector<int> sortArray(vector<int>& nums) { vector<int> t(nums.size()); function<void(int, int)> mergeSort = [&](int l, int r) { if (l + 1 >= r) return; int m = l + (r - l) / 2; mergeSort(l, m); mergeSort(m, r); int i1 = l; int i2 = m; int index = 0; while (i1 < m || i2 < r) if (i2 == r || (i1 < m && nums[i1] < nums[i2])) t[index++] = nums[i1++]; else t[index++] = nums[i2++]; std::copy(begin(t), begin(t) + index, begin(nums) + l); }; mergeSort(0, nums.size()); return nums; } }; |
Solution 4: BST
Time complexity: (nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public: vector<int> sortArray(vector<int>& nums) { multiset<int> s(begin(nums), end(nums)); return {begin(s), end(s)}; } }; |