HackMD
912.Sort an Array
tags: Medium,Array,Sorting
題目描述
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
解答
Javascript
function sortArray(nums) {
if (nums.length <= 1) return nums;
const mid = ~~(nums.length / 2);
const left = nums.slice(0, mid);
const right = nums.slice(mid);
return merge(sortArray(left), sortArray(right));
}
function merge(left, right) {
const result = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
result.push(...left.slice(leftIndex));
result.push(...right.slice(rightIndex));
return result;
}
寫個merge sort好了比較簡單。
MarsgoatMar 1, 2023
Python
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def quickSort(left, right):
if left >= right:
return
l, r = left, right
mid = (r - l) // 2 + l
pivot = nums[mid]
while r >= l:
while r >= l and nums[l] < pivot: l += 1
while r >= l and nums[r] > pivot: r -= 1
if r >= l:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
quickSort(left, r)
quickSort(l, right)
quickSort(0, len(nums) - 1)
return nums
Ron ChenThu, Mar 2, 2023
