面試題 17.14. 最小K個數
設計一個算法，找出數組中最小的k個數。以任意順序返回這k個數均可。
示例：
輸入： arr = [1,3,5,7,2,4,6,8], k = 4
輸出： [1,2,3,4]
提示：
- 0 <= len(arr) <= 100000
- 0 <= k <= min(100000, len(arr))
解題思路
通過快速選擇，我們可以將數組劃分成兩個區間A[l,i]，B[i+1,r],A區間的所有元素均小于B區間
- 如果k剛好就是A區間的長度的話，說明我們已經找到了最小的k個數字
- 如果k大于A區間長度的話，說明我們要找的除了整個A區間以外，還有B區間的一部分元素
- 如果k小于A區間長度的話，說明我們需要找的數全部在A區間里面
代碼
class Solution {public int[] smallestK(int[] arr, int k) {int[] res=new int[k];int l=0,r=arr.length-1,w=k;while(l<r){int i=partition(arr,l,r);int n=i-l+1;if(n==k){break;}else if(n<k){l=i+1;k-=n;}else {r=i;}}System.arraycopy(arr,0,res,0,w);return res;}public int partition(int[] arr, int l,int r) {int t=arr[l];while(l<r){while(l<r&&arr[r]>=t)r--;arr[l]=arr[r];while(l<r&&arr[l]<=t)l++;arr[r]=arr[l];}arr[l]=t;return l;}
}
