===========================================================
Description:
Given an array of integers nums, sort the array in ascending order and return it.
You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.
Example 1:
Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).
Example 2:
Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessairly unique.
Constraints:
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
===========================================================
Solution:
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
private:
void mergeSort(vector<int>& A, int l, int r) {
if (l >= r)
return;
const int m = (l + r) / 2;
mergeSort(A, l, m);
mergeSort(A, m + 1, r);
merge(A, l, m, r);
}
void merge(vector<int>& A, int l, int m, int r) {
vector<int> sorted(r - l + 1);
int k = 0; // sorted's index
int i = l; // left's index
int j = m + 1; // right's index
while (i <= m && j <= r)
if (A[i] < A[j])
sorted[k++] = A[i++];
else
sorted[k++] = A[j++];
// put possible remaining left part to the sorted array
while (i <= m)
sorted[k++] = A[i++];
// put possible remaining right part to the sorted array
while (j <= r)
sorted[k++] = A[j++];
copy(begin(sorted), end(sorted), begin(A) + l);
}
};
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/sort-an-array/
Top comments (0)