最小的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]

二、排序法

2.1  思路分析

对数组进行排序，将前k个元素存储到新的数组中，并返回即可。

2.2  代码实现

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

2.3  复杂度分析

时间复杂度为O(nlogn)，其中n是数组arr的长度，算法的时间复杂度即排序的时间复杂度；空间复杂度为O(n)，申请了k个元素的空间；

三、快速排序法 

3.1  思路分析

太长了，就加在注释上了。

3.2  代码实现

class Solution { public int[] getLeastNumbers(int[] arr, int k) { //首先进行边界判断 if(arr == null || arr.length == 0 || k <= 0 || k > arr.length) //返回一个int类型的空数组 return new int[0]; //只要不是上述情况，就一定有解，直接返回k个最小数 return quickSearch(arr,0,arr.length-1,k-1); } int[] quickSearch(int[] arr,int left,int right,int index) { //快排一次，返回j，此时j的左边的数小于等于nums[j]，j的右边的数大于等于nums[j] int j = partition(arr,left,right); //判断j是否是要找的下标，是的话，就返回结果 if(j == index) { return Arrays.copyOf(arr,j+1); } //不是就继续找，j>index，去j的左侧去找，j < index，去j的右侧去找 return j > index ? quickSearch(arr,left,j-1,index) : quickSearch(arr,j+1,right,index); } int partition(int[] arr,int left,int right) { //选择一个基准值 int pivot = arr[left]; int i = left; int j = right+1; //然后就开始移动元素，将小于等于nums[j]的放左边，大于等于nums[j]的放右边 while(true) { while(++i <= right && arr[i] < pivot); while(--j >= left && arr[j] > pivot); if(i >= j) break; //交换 int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } //排完序之后，将arr[left]与小于pivot的arr[j]交换 arr[left] = arr[j]; arr[j] = pivot; return j; } }

3.3  复杂度分析

时间复杂度为O(N)，其中N为数组元素的个数，第一次找基准值 j 需要遍历整个数组，若j > index，需要在left ~ j-1内找，若j < index，需要在j+1 ~ right内找，也就是每次调用partition遍历的元素数组是上次遍历的1/2，因此时间复杂度为N+N/2+...+N/N = 2N，故时间复杂度为O(N)。空间复杂度期望为O(logN)，递归调用的期望深度为O(logN)，每层需要的空间为O(1)，只有常数个变量。最坏情况下，空间复杂度为O(N)。

3.4  趁热打铁，利用快排对数组排序

//现在给你一个数组，要求利用快速排序实现数组的从小到大排序 class Solution { public static void main(String[] args) { int[] arr = {3,5,7,2,1,9,8,6}; arraySort(arr,0,arr.length-1); for(int i : arr) { System.out.print(i+" "); } } public static void arraySort(int[] arr,int left,int right) { if(arr == null || arr.length == 0) { return; } quickSearch(arr,left,right); } private static void quickSearch(int[] arr, int left, int right) { if(left >= right) return; int pivot = arr[left]; int i = left; int j = right+1; while(true) { while(++i <= right && arr[i] < pivot); while(--j >= left && arr[j] > pivot); if(i >= j) { break; } int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } arr[left] = arr[j]; arr[j] = pivot; quickSearch(arr,left,j-1); quickSearch(arr,j+1,right); } }

四、PriorityQueue

4.1  思路分析

PriorityQueue默认实现小根堆，即根结点最小，若要得到最小的k个元素，需要将数组中所有值都入队，然后再取前k个元素返回；若我们自定义比较器，实现大根堆，即根结点最大，那么先将k个元素加入到队列中，之后的元素，若大于队首元素就不管了，若小于队首元素就将队首元素出队，将该元素加入，那么最后队列中只会剩下k个最小的数；

4.2  代码实现

class Solution { public int[] getLeastNumbers(int[] arr, int k) { //边界条件判断 if(arr == null || arr.length == 0 || k <= 0 || k > arr.length) return new int[0]; //新建PriorityQueue对象，自己指定比较器实现降序模式 //Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1); //利用PriorityQueue的构造方法，指定比较器实现降序模式 Queue<Integer> pq = new PriorityQueue<>(11,new Comparator<Integer>() { public int compare(Integer v1,Integer v2) { return v2 - v1; } }); //保持队列容量始终为k，开始向队列添加元素 for(int num : arr) { if(pq.size() < k) { pq.offer(num); } else if(num < pq.peek()) { pq.poll(); pq.offer(num); } } //现在队列中是k个降序的最小元素 int[] res = new int[k]; for(int i = 0; i < k; i++) { res[i] = pq.poll(); } return res; } }

4.3  复杂度分析

时间复杂度为O(NlogK)，这个还不知道怎么算；空间复杂度为O(2K)吧，队列存储K个元素，返回结论时申请了K个空间。

五、学习地址

作者：sweetiee

链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/