「LeetCode每日一题」—— 912. 排序数组
912. 排序数组
链接:https://leetcode-cn.com/problems/sort-an-array/
难度:中等
题目
给你一个整数数组 nums,请你将该数组升序排列。
示例 1:
输入:nums = [5,2,3,1]
输出:[1,2,3,5]
示例 2:
输入:nums = [5,1,1,2,0,0]
输出:[0,0,1,1,2,5]
提示:
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
思路
这题,见方案。
方案代码
调用库函数:
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
return sorted(nums)
快排方案:
class Solution:
def randomized_partition(self, nums, l, r):
pivot = random.randint(l, r)
nums[pivot], nums[r] = nums[r], nums[pivot]
i = l - 1
for j in range(l, r):
if nums[j] < nums[r]:
i += 1
nums[j], nums[i] = nums[i], nums[j]
i += 1
nums[i], nums[r] = nums[r], nums[i]
return i
def randomized_quicksort(self, nums, l, r):
if r - l <= 0:
return
mid = self.randomized_partition(nums, l, r)
self.randomized_quicksort(nums, l, mid - 1)
self.randomized_quicksort(nums, mid + 1, r)
def sortArray(self, nums: List[int]) -> List[int]:
self.randomized_quicksort(nums, 0, len(nums) - 1)
return nums
堆排序方案:
class Solution:
def max_heapify(self, heap, root, heap_len):
p = root
while p * 2 + 1 < heap_len:
l, r = p * 2 + 1, p * 2 + 2
if heap_len <= r or heap[r] < heap[l]:
nex = l
else:
nex = r
if heap[p] < heap[nex]:
heap[p], heap[nex] = heap[nex], heap[p]
p = nex
else:
break
def build_heap(self, heap):
for i in range(len(heap) - 1, -1, -1):
self.max_heapify(heap, i, len(heap))
def heap_sort(self, nums):
self.build_heap(nums)
for i in range(len(nums) - 1, -1, -1):
nums[i], nums[0] = nums[0], nums[i]
self.max_heapify(nums, 0, i)
def sortArray(self, nums: List[int]) -> List[int]:
self.heap_sort(nums)
return nums
归并排序方案:
class Solution:
def merge_sort(self, nums, l, r):
if l == r:
return
mid = (l + r) // 2
self.merge_sort(nums, l, mid)
self.merge_sort(nums, mid + 1, r)
tmp = []
i, j = l, mid + 1
while i <= mid or j <= r:
if i > mid or (j <= r and nums[j] < nums[i]):
tmp.append(nums[j])
j += 1
else:
tmp.append(nums[i])
i += 1
nums[l: r + 1] = tmp
def sortArray(self, nums: List[int]) -> List[int]:
self.merge_sort(nums, 0, len(nums) - 1)
return nums
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/266.html
您必须登录才能发表评论。