Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/912.html
912. Sort an Array (Medium)
Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: [5,2,3,1] Output: [1,2,3,5]
Example 2:
Input: [5,1,1,2,0,0] Output: [0,0,1,1,2,5]
Note:
1 <= A.length <= 10000-50000 <= A[i] <= 50000
Solution 1. STL
// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums;
}
};
Solution 2. Quick Sort
// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN) on average
// Space: O(1)
class Solution {
private:
int partition(vector<int> &nums, int L, int R, int pivot) {
swap(nums[pivot], nums[R]);
for (int i = L; i < R; ++i) {
if (nums[i] >= nums[R]) continue;
swap(nums[i], nums[L++]);
}
swap(nums[L], nums[R]);
return L;
}
void quickSort(vector<int> &nums, int L, int R) {
if (L >= R) return;
int M = partition(nums, L, R, rand() % (R - L + 1) + L);
quickSort(nums, L, M - 1);
quickSort(nums, M + 1, R);
}
public:
vector<int> sortArray(vector<int>& nums) {
srand (time(NULL));
quickSort(nums, 0, nums.size() - 1);
return nums;
}
};
Solution 3. Merge Sort
// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(N)
class Solution {
private:
vector<int> tmp;
void mergeSort(vector<int> &nums, int start, int end) {
if (start + 1 >= end) return;
int mid = (start + end) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid, end);
for (int i = start, j = mid, k = 0; i < mid || j < end; ++k) {
tmp[k] = (i >= mid || (j < end && nums[j] < nums[i])) ? nums[j++] : nums[i++];
}
for (int i = start; i < end; ++i) nums[i] = tmp[i - start];
}
public:
vector<int> sortArray(vector<int>& nums) {
tmp = vector<int>(nums.size());
mergeSort(nums, 0, nums.size());
return nums;
}
};
Solution 4. Heap Sort
// OJ: https://leetcode.com/problems/sort-an-array/
// Time: O(NlogN)
// Space: O(1)
class Solution {
private:
void heapify(vector<int> &nums) {
for (int i = nums.size() / 2 - 1; i >= 0; --i)
siftDown(nums, i, nums.size());
}
void siftDown(vector<int> &nums, int hole, int end) {
int next = 2 * hole + 1;
while (next < end) {
if (next + 1 < end && nums[next + 1] > nums[next]) ++next;
if (nums[hole] > nums[next]) break;
swap(nums[hole], nums[next]);
hole = next;
next = 2 * next + 1;
}
}
public:
vector<int> sortArray(vector<int>& nums) {
heapify(nums);
for (int i = nums.size() - 1; i > 0; --i) {
swap(nums[0], nums[i]);
siftDown(nums, 0, i);
}
return nums;
}
};
-
class Solution { public List<Integer> sortArray(int[] nums) { return mergeSort(nums); } public List<Integer> mergeSort(int[] nums) { int length = nums.length; if (length == 1) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[0]); return list; } else { int halfLength = length / 2; int[] nums1 = new int[halfLength]; int[] nums2 = new int[length - halfLength]; for (int i = 0; i < halfLength; i++) nums1[i] = nums[i]; for (int i = halfLength; i < length; i++) nums2[i - halfLength] = nums[i]; List<Integer> list1 = mergeSort(nums1); List<Integer> list2 = mergeSort(nums2); return merge(list1, list2); } } public List<Integer> merge(List<Integer> list1, List<Integer> list2) { List<Integer> mergedList = new ArrayList<Integer>(); int size1 = list1.size(), size2 = list2.size(); int index1 = 0, index2 = 0; while (index1 < size1 && index2 < size2) { int num1 = list1.get(index1), num2 = list2.get(index2); if (num1 <= num2) { mergedList.add(num1); index1++; } else { mergedList.add(num2); index2++; } } while (index1 < size1) { mergedList.add(list1.get(index1)); index1++; } while (index2 < size2) { mergedList.add(list2.get(index2)); index2++; } return mergedList; } } ############ class Solution { private int[] nums; public int[] sortArray(int[] nums) { this.nums = nums; quikcSort(0, nums.length - 1); return nums; } private void quikcSort(int l, int r) { if (l >= r) { return; } int x = nums[(l + r) >> 1]; int i = l - 1, j = r + 1; while (i < j) { while (nums[++i] < x) { } while (nums[--j] > x) { } if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } quikcSort(l, j); quikcSort(j + 1, r); } } -
// OJ: https://leetcode.com/problems/sort-an-array/ // Time: O(NlogN) // Space: O(1) class Solution { public: vector<int> sortArray(vector<int>& nums) { sort(nums.begin(), nums.end()); return nums; } }; -
class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(l, r): if l >= r: return x = nums[randint(l, r)] i, j, k = l - 1, r + 1, l while k < j: if nums[k] < x: nums[i + 1], nums[k] = nums[k], nums[i + 1] i, k = i + 1, k + 1 elif nums[k] > x: j -= 1 nums[j], nums[k] = nums[k], nums[j] else: k = k + 1 quick_sort(l, i) quick_sort(j, r) quick_sort(0, len(nums) - 1) return nums -
func sortArray(nums []int) []int { quickSort(nums, 0, len(nums)-1) return nums } func quickSort(nums []int, l, r int) { if l >= r { return } i, j := l-1, r+1 x := nums[(l+r)>>1] for i < j { for { i++ if nums[i] >= x { break } } for { j-- if nums[j] <= x { break } } if i < j { nums[i], nums[j] = nums[j], nums[i] } } quickSort(nums, l, j) quickSort(nums, j+1, r) } -
function sortArray(nums: number[]): number[] { function quickSort(l: number, r: number) { if (l >= r) { return; } let i = l - 1; let j = r + 1; const x = nums[(l + r) >> 1]; while (i < j) { while (nums[++i] < x); while (nums[--j] > x); if (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; } } quickSort(l, j); quickSort(j + 1, r); } const n = nums.length; quickSort(0, n - 1); return nums; } -
/** * @param {number[]} nums * @return {number[]} */ var sortArray = function (nums) { function quickSort(l, r) { if (l >= r) { return; } let i = l - 1; let j = r + 1; const x = nums[(l + r) >> 1]; while (i < j) { while (nums[++i] < x); while (nums[--j] > x); if (i < j) { [nums[i], nums[j]] = [nums[j], nums[i]]; } } quickSort(l, j); quickSort(j + 1, r); } const n = nums.length; quickSort(0, n - 1); return nums; };