题目

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof

输入整数数组 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

代码和思路

快速排序

找出数组中的最小 k 个数，直接对数组进行排序，选择前 k 个数即可

  1. class Solution:
  2.     def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
  3.         def quick_sort(a):
  4.             _quick_sort_between(a, 0, len(a)-1)
  6.         def partition(a, low, high):
  7.             p = a[high]
  8.             i = low
  9.             for j in range(low, high):
  10.                 if a[j] < p:
  11.                     a[i], a[j] = a[j], a[i]
  12.                     i += 1
  13.             a[i], a[high] = a[high], a[i]
  14.             return i 
  16.         def _quick_sort_between(a, low, high):
  17.             if low < high:
  18.                 m = partition(a, low, high)
  19.                 _quick_sort_between(a, low, m-1)
  20.                 _quick_sort_between(a, m+1, high)
  22.         quick_sort(arr)
  23.         return arr[:k]

快速选择

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/
快速排序的变种，快速排序需要选择一个分区点（分区索引）

首先对数组进行快速排序，

  • 若 分区点索引 m 与 k 相等，那说明
  • 若 k > m，说明前半部分都是最小的 k 个数，但是还不够，需要对右侧进行递归分区

  • 若 k < m，最小的 k 个数都在前半部分，只需对前半部分进行递归分区即可

    1. class Solution:
    2.   def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
    3.       def quick_sort(a, k):
    4.           _quick_sort_between(a, 0, len(a)-1, k)
    6.       def partition(a, low, high):
    7.           p = a[high]
    8.           i = low
    9.           for j in range(low, high):
    10.               if a[j] < p:
    11.                   a[i], a[j] = a[j], a[i]
    12.                   i += 1
    13.           a[i], a[high] = a[high], a[i]
    14.           return i 
    16.       def _quick_sort_between(a, low, high, k):
    17.           if low < high:
    18.               m = partition(a, low, high) # 分区点
    19.               if k == m:
    20.                   return
    21.               elif k > m: # 前半部分都是最小的 k 个数，只需对后面那部分进行递归分区即可
    22.                   _quick_sort_between(a, m+1, high, k)
    23.               else:  # 最小的 k 个数都在前半部分，只需对前半部分进行递归分区即可
    24.                   _quick_sort_between(a, low, m-1, k)
    26.       quick_sort(arr, k)
    27.       return arr[:k]