1. 题目

原题链接

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

Related Topics 堆 分治算法
👍 242 👎 0

2. 题解

2.1 解法1: 基于快速排序思想

需要将数组划分为 最小的 k 个数 和 其他数字 两部分即可，而快速排序的哨兵划分可完成此目标
每次快排划分后, 进行判断:

1. 若 k < i，代表第 k + 1 小的数字在 左子数组 中，则递归左子数组；
2. 若 k > i ，代表第 k + 1 小的数字在 右子数组 中，则递归右子数组；
3. 若 k = i ，代表此时 arr[k] 即为第 k + 1 小的数字，则直接返回数组前 k 个数字即可；

    class Solution {public int[] getLeastNumbers(int[] arr, int k) {quickSort(arr, 0, arr.length - 1, k);int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = arr[i];}return ans;}public void quickSort(int[] nums, int left, int right, int k) {if (left >= right) return;int pivot = nums[left];int i = left, j = right;while (i < j) {while (i < j && nums[j] >= pivot) j--;nums[i] = nums[j];while (i < j && nums[i] <= pivot) i++;nums[j] = nums[i];}nums[i] = pivot;if (i == k) {return;} else if (i < k) {quickSort(nums, i + 1, right, k);} else {quickSort(nums, left, i - 1, k);}}}

写法2:

    class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0) {return new int[0];}if (arr.length < k) {return arr;}quickPartition(arr, 0, arr.length - 1, k);int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = arr[i];}return ans;}public void quickPartition(int[] arr, int left, int right, int k) {if (left >= right) {return;}int pivot = arr[left];int i = left, j = right;while (i < j) {while (i < j && arr[j] >= pivot) {j--;}while (i < j && arr[i] <= pivot) {i++;}swap(arr, i, j);}swap(arr, i, left);if (k == i) {return;} else if (k < i) {quickPartition(arr, left, i - 1, k);} else {quickPartition(arr, i + 1, right, k);}}public void swap(int[] arr, int a, int b) {int temp = arr[a];arr[a] = arr[b];arr[b] = temp;}}

参考:
剑指 Offer 40. 最小的 k 个数（基于快速排序的数组划分，清晰图解）
Top K 的两种经典解法（堆/快排变形）与优劣比较

2.2 解法2: 优先队列(堆)

1. 建立一个大小为 k 的最大堆, 然后依次向其中加入元素, 结束时中堆内的元素为前k小的元素

    class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k == 0) {return new int[0];}if (arr.length < k) {return arr;}PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});for (int i = 0; i < k; i++) {heap.offer(arr[i]);}for (int i = k; i < arr.length; i++) {if (heap.peek() > arr[i]) {heap.poll();heap.offer(arr[i]);}}int[] ans = new int[k];int i = 0;while (!heap.isEmpty()) {ans[i++] = heap.poll();}return ans;}}

参考:
Top K 的两种经典解法（堆/快排变形）与优劣比较

2.3 解法3: 排序再取数

    class Solution {public int[] getLeastNumbers(int[] arr, int k) {Arrays.sort(arr);int[] ans = new int[k];for (int i = 0; i < k; i++) {ans[i] = arr[i];}return ans;}}