剑指offer40最小的k个数

最小的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） 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

法一：

堆排序，建立最小堆，只需要弹出指定数量的元素即可。

private int[] method1(int[] arr, int k) { // 法一：建立最小堆 buildHeap(arr, arr.length - 1); int n = arr.length - 1; int[] res = new int[k]; int resIdx = 0; for (int i = n; i >= arr.length - k; i--) { res[resIdx++] = arr[0]; swap(arr, 0, i); heapify(arr, 0, --n); } return res; } private void buildHeap(int[] arr, int e) { // int e = arr.length - 1; for (int i = e / 2; i >= 0; i--) { heapify(arr, i, e); } } private void heapify(int[] arr, int idx, int e) { int minIdx = idx; int left = idx * 2 + 1; int right = idx * 2 + 2; if (left >= 0 && left <= e && arr[left] < arr[minIdx]) { minIdx = left; } if (right >= 0 && right <= e && arr[right] < arr[minIdx]) { minIdx = right; } if (minIdx != idx) { swap(arr, minIdx, idx); heapify(arr, minIdx, e); } } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

法二：

直接sort

private int[] method2(int[] arr, int k) { Arrays.sort(arr); int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = arr[i]; } return res; }

法三：

建立大顶堆，先存储k个元素。

之后的每个元素和大顶堆的堆首元素比较，如果比堆首元素小，放入堆，调整堆。

最后堆里放的元素就是k个最小元素。

public int[] getLeastNumbers(int[] arr, int k) { if (k <= 0) { return new int[0]; } if (k == arr.length) { return arr; } return method3(arr, k); } private int[] method3(int[] arr, int k) { // 拷贝 int[] res = Arrays.copyOf(arr, k); // 建立大顶堆 buildMaxHeap(res, k - 1); for (int i = k; i < arr.length; i++) { // 如果比当前堆最大元素还小，那么改变当前堆的最大元素 if (arr[i] < res[0]) { res[0] = arr[i]; maxHeapify(res, 0, res.length - 1); } } return res; } private void buildMaxHeap(int[] arr, int e) { for (int i = e / 2; i >= 0; i--) { maxHeapify(arr, i, e); } } private void maxHeapify(int[] arr, int idx, int e) { int maxIdx = idx; int left = idx * 2 + 1; int right = idx * 2 + 2; if (left >= 0 && left <= e && arr[left] > arr[maxIdx]) { maxIdx = left; } if (right >= 0 && right <= e && arr[right] > arr[maxIdx]) { maxIdx = right; } if (maxIdx != idx) { swap(arr, maxIdx, idx); maxHeapify(arr, maxIdx, e); } }

法四：

快速选择的思想。

因为快速排序每次可以找到比基准值小的数。

假设比基准值小的数的数量为num。

如果这个num == k，表示比基准值小的数的数量刚好等于我们需要的数量，那么直接返回。

如果num > k，表示比基准值小的数的数量太多了，我们不需要那么多，那就再递归遍历左边数组即可。

如果num < k，表示比基准值小的数不够我们需要的数量k，那么 就再递归遍历右边数组即可

public int[] getLeastNumbers(int[] arr, int k) { if (k <= 0) { return new int[0]; } if (k == arr.length) { return arr; } method4(arr, 0, arr.length - 1, k); return toNewArr(arr, k); } private void method4(int[] arr, int s, int e, int k) { // 先排序一次 int num = sort(arr, s, e); // 如果刚好比中间数小的有要求的那么多 if (num == k) { return ; } else if (num > k) { // 如果比中间小的数num多于k，那么再去递归 method4(arr, s, num, k); } else { // 如果比中间小的数少于k，那么应该左边全部，加上右边 method4(arr, num + 1, e, k); } } private int[] toNewArr(int[] arr, int k) { int[] res = new int[k]; for (int i = 0; i < k; i++) { res[i] = arr[i]; } return res; } /** * 快速排序的部分 */ private int sort(int[] arr, int s, int e) { int i = s, j = e; int key = arr[s]; while (i < j) { while (i < j && arr[j] >= key) { j--; } if (i < j) { arr[i++] = arr[j]; } while (i < j && arr[i] <= key) { i++; } if (i < j) { arr[j--] = arr[i]; } } arr[i] = key; return i; }