剑指 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]限制：
0 <= k <= arr.length <= 100000 <= arr[i] <= 10000解题思路 优先队列 快排
class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(k==0 || arr.length==0){ return new int[0]; } // 默认是小根堆 实现大根堆 需要重写一下比较器 Queue<Integer> pq = new PriorityQueue<>((v1,v2)->v2-v1); for(int num:arr){ if(pq.size()<k){ pq.offer(num); }else{ if(pq.peek()>num){ pq.poll(); pq.offer(num); } } } // 返回堆中的元素 int[] res = new int[pq.size()]; int idx = 0; for(int num:pq){ res[idx++] = num; } return res; } }快排
class Solution { public int[] getLeastNumbers(int[] arr, int k) { if(k==0 || arr.length==0){ return new int[0]; } // 表示要我们要找的是下标为k-1的数 return quickSearch(arr,0,arr.length-1,k-1); } private int[] quickSearch(int[] nums,int lo,int hi,int k){ int j = partition(nums,lo,hi); if(j==k){ return Arrays.copyOf(nums,j+1); } return j>k?quickSearch(nums,lo,j-1,k):quickSearch(nums,j+1,hi,k); } private int partition(int[] nums,int lo,int hi){ int v = nums[lo]; int i=lo,j=hi+1; while(true){ //找到左侧第一个>=v的数 while(++i<=hi&&nums[i]<v); //找到右侧第一个小于=v的数 //example v=5 num[i]=num[j]=5 i=j num[i]=6 nums[j]=4 i>j; while(--j>=lo && nums[j]>v); if(i>=j){ break; } int t = nums[j]; nums[j]=nums[i]; nums[i]=t; } nums[lo]=nums[j]; nums[j]=v; return j; } }