[剑指 Offer 40]最小的k个数

[剑指 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]
1
2
3
4
5
6
7
8
9

题解

利用快速排序划分数组

• 首先判断 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---