最小k个数

https://leetcode-cn.com/problems/smallest-k-lcci/

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]

思路

考察快速排序的思想

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        # 快速排序思想
        if len(arr) == 0: return []
        idx = self.partition(arr, 0, len(arr) - 1)
        if idx == k:
            return arr[:idx]
        elif idx < k:
            return arr[:idx] + self.smallestK(arr[idx:], k - idx)
        else:
            # idx > k
            return self.smallestK(arr[:idx], k)
    def partition(self, array, l, r):
        pivot = array[r]
        i = l - 1
        for j in range(l, r):
            if array[j] <= pivot:
                i += 1
                array[i], array[j] = array[j], array[i]
        array[i+1], array[r] = array[r], array[i+1]
        return i+1

快速排序

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)
def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            # 控制升序还是降序
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i+1]
    # print(array)
    return i + 1
if __name__ == "__main__":
    array = [10, 5, 3, 1, 7]
    quick_sort(array, 0, len(array)-1)
    print(array)