剑指Offer40-最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
-
0 <= k <= arr.length <= 10000
-
0 <= arr[i] <= 10000
来源：力扣（LeetCode）
链接：力扣
一解
采用基于快排的数组划分法（本题解需要先了解快排思想），先利用快排进行排序，如果发现：
-
基准数的索引 i < k：说明需要对 i 的右边进行快排
-
基准数的索引 i > k：说明需要对 i 的左边进行快排
以arr = [3,2,1], k = 2为例，设基准数为 3 ：
由于 i == k ，可直接返回 arr[:k] 。
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k >= len(arr) : return arr
def quick_sort(l, r):
i, j = l, r
# 选取 l 为哨兵
while i < j:
while i < j and arr[j] >= arr[l]: j -= 1
while i < j and arr[i] <= arr[l]: i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i], arr[l] = arr[l], arr[i]
if k < i: return quick_sort(l, i - 1)
if k > i: return quick_sort(i + 1, r)
return arr[:k]
return quick_sort(0, len(arr) - 1)