刚找回了账号，好久没用了，界面都不认识了。。
打算重新开始更新啦，偶尔回来复习一下，啊哈哈
回归第一题，RT，利用快排的思路求数组中的TopK元素，
（注意：题中是要求反馈前TopK个元素，不是第TopK个元素）
思路：先默写快排的Partition，然后修改下快排的QuickSort函数， 每次判断当前基准划分元素所在索引mid，计算mid-low+1 = num 如果num > k, 说明k在mid左边的子数组中，调用self.Quicksort(A,low,mid-1,k) 如果num < k, 说明k在mid右边的子数组中，调用self.Quicksort(A,mid+1,high,k-num) 如果num == k, 说明找到了前k个，递归出口
边界条件： 注意如果当前的A[low:high]数组长度正好等于k，直接return
代码如下：
class Solution: def Partition(self, A, low, high): pivot = A[low] while low < high: while low < high and A[high] >= pivot: high -= 1 A[low] = A[high] while low < high and A[low] < pivot: low += 1 A[high] = A[low] A[low] = pivot return low def Quicksort(self, A, low, high, k): if low < high: mid = self.Partition(A,low,high) if high - low + 1 == k: return num = mid - low + 1 if k < num: self.Quicksort(A,low,mid-1,k) elif k > num: self.Quicksort(A,mid+1,high,k-num) elif k == num: return def getLeastNumbers(self, arr, k): if k == 0: return [] self.Quicksort(arr,0,len(arr)-1,k) return arr[:k]
