[剑指 Offer 40]最小的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]

题解

利用快速排序划分数组

• 首先判断 k 和 数组长度的关系，k >= arr.length 直接返回
• 然后整个数组进行快速排序
• 以数字第一个元素作为基准
• 进行循环交换，循环条件为i < j
  • 从数组后边开始，找到第一个小于基准数的元素
  • 从第一个元素开始，找到第一个大于基准数的元素
  • 交换这两个元素，然后将基准数交换到正确位置
• 判断 i 和 k 的关系
  • 如果相等，直接返回 i 前边的所有元素，即为最小的k个数
  • 否则，根据 i 的大小，继续划分对应部分，使 i==k

class Solution {public int[] getLeastNumbers(int[] arr, int k) {if (k >= arr.length) return arr;return quickSort(arr, k, 0, arr.length - 1);}//快速排序private int[] quickSort(int[] arr, int k, int l, int r) {int i = l, j = r;while (i < j) {while (i < j && arr[j] >= arr[l]) j--;while (i < j && arr[i] <= arr[l]) i++;swap(arr, i, j);}swap(arr, i, l);//判断i索引，等于k就返回，否则继续划分if (i > k) return quickSort(arr, k, l, i - 1);if (i < k) return quickSort(arr, k, i + 1, r);return Arrays.copyOf(arr, k);}//交换private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}