1000021-smallest-k-lcci.md

1000021. 最小K个数 - medium

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

示例：

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

提示：

• 0 <= len(arr) <= 100000
• 0 <= k <= min(100000, len(arr))

thinking

1. 快排加选择

refer to 215. 数组中的第K个最大元素

code

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        
        if not arr:
            return arr

        l, h = 0, len(arr) - 1
        m = self.part(arr, l, h)
        
        while m != k:
            if m < k:
                l = m + 1
            else:
                h = m - 1
            m = self.part(arr, l, h)
        return arr[:m]

    def quick_sort(self, arr: List[int], l: int, r: int):
        if l >= r:
            return

        m = self.part(arr, l, r)
        self.quick_sort(arr, l, m - 1)
        self.quick_sort(arr, m + 1, r)

    def part(self, arr: List[int], l: int, r: int) -> int:
        p = arr[l]

        while l < r:
            while arr[r] >= p and l < r:
                r -= 1
            arr[l] = arr[r]

            while arr[l] < p and l < r:
                l += 1
            arr[r] = arr[l]
        
        arr[l] = p
        return l