题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
快排，判断当前是不是第k个就可以了，因为顺序可以乱
import java.util.ArrayList;
import java.util.*;public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
quickSort(input,0,input.length-1,k);
ArrayList<Integer> res=new ArrayList<>();
for(int i=0;i<k;i++){
res.add(input[i]);
}
return res;
}
void swap(int []arr,int i,int j){
if(i!=j){
arr[i]^=arr[j];
arr[j]^=arr[i];
arr[i]^=arr[j];
}
}
void quickSort(int []arr ,int start,int end,int k){
if(start<end){
int key=arr[start];
int i=start;
for(int j=i+1;j<=end;j++){
if(arr[j]<=key){
swap(arr,j,++i);
}
}
arr[start]=arr[i];
arr[i]=key;
if(i>k){
quickSort(arr,0,i-1,k);}
else if(i<k)
quickSort(arr,i+1,end,k);
else
return;
}
return;
}
}
）
