剑指Offer40-最小的k个数

剑指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) 

            

关闭