题目地址(40. 最小的k个数)

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

题目描述

  1. 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
  5. 示例 1：
  7. 输入：arr = [3,2,1], k = 2
  8. 输出：[1,2] 或者 [2,1]
  11. 示例 2：
  13. 输入：arr = [0,1,2,1], k = 1
  14. 输出：[0]
  18. 限制：
  20. 0 <= k <= arr.length <= 10000
  21. 0 <= arr[i] <= 10000

前置知识


公司

  • 暂无

思路

关键点


代码

  • 语言支持：Java

Java Code:
api大法 或者手写一下快排

  2. class Solution {
  3.     public int[] getLeastNumbers(int[] arr, int k) {
  4.         Arrays.sort(arr);
  5.         return Arrays.copyOf(arr, k);
  6.     }
  7. }
  1. class Solution {
  2.     public int[] getLeastNumbers(int[] arr, int k) {
  3.         kuai(arr, 0, arr.length - 1);
  4.         return Arrays.copyOf(arr, k);
  5.     }
  6.     public void kuai(int[] ints, int left, int right) {
  7.         //递归终止条件
  8.         if (left >= right) {
  9.             return;
  10.         }
  11.         int i = left;
  12.         int j = right;
  13.         //基准值 最左边的值
  14.         int base = ints[left];
  15.         while (i < j) {
  16.             //这里的顺序不能反 必须是先-- 假设数组为 5 4 3 2 6 如果是++先 那么i就直接遍历到6才会停下 然后外层再和left交换 就不能正确的排序了
  17.             while (i < j && ints[j] >= base) {
  18.                 j--;
  19.             }
  20.             while (i < j && ints[i] <= base) {
  21.                 i++;
  22.             }
  23.             //交换i 第一个大于base的值 和j 第一个小于base的值
  24.             int tmp = ints[i];
  25.             ints[i] = ints[j];
  26.             ints[j] = tmp;
  27.         }
  28.         // 交换i和left  这样base的左边都是小于他的 右边都是大于他的
  29.         int tmp = ints[i];
  30.         ints[i] = ints[left];
  31.         ints[left] = tmp;
  32.         //递归调用左边和右边
  33.         kuai(ints, left, i - 1);
  34.         kuai(ints, i+1, right);
  35.     }
  36. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 40. 最小的k个数 - 图1
  • 空间复杂度：剑指 Offer 40. 最小的k个数 - 图2#card=math&code=O%28n%29&id=TWZmX)