Description
https://leetcode.com/problems/sort-an-array/
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
Explanation
Use quick sort or merge sort.
Python Solution
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
self.quick_sort(nums, 0, len(nums) - 1)
return nums
def quick_sort(self, nums, left, right):
if left >= right:
return
pivot = self.partition(nums, left, right)
self.quick_sort(nums, left, pivot - 1)
self.quick_sort(nums, pivot + 1, right)
def partition(self, nums, left, right):
pivot = nums[right]
i = left
for j in range(left, right):
if nums[j] < pivot:
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[right] = nums[right], nums[i]
return i
- Time complexity: O(N logN).
- Space complexity: O(N).