1.快排划分思路的解法
特别注意k=0的情况
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if not arr or k == 0:
return []
self.partitionK(arr, 0, len(arr)-1, k)
return arr[:k]
def partitionK(self, nums, l, r, k):
index = self.partition(nums, l, r)
length = index - l + 1
# print("index,nums,l,r,k, length",index,nums,l,r,k, length)
if k > length:
self.partitionK(nums, index+1, r, k-length)
if k < length:
self.partitionK(nums, l, index-1, k)
def partition(self, nums, l, r):
self.swap(nums, l, l+(r-l)//2)
# print("partition,nums", nums)
pivot = l
index = l+1
for i in range(index, r+1):
# print('i,index,nums', i,index,nums)
if nums[i] < nums[pivot]:
self.swap(nums, index, i)
index += 1
# print("partition2,nums", nums)
self.swap(nums, pivot, index-1)
return index-1
def swap(self, nums, i, j):
nums[i],nums[j] = nums[j], nums[i]
