1 题目描述
输入 n 个整数，找出其中最小的 K 个数。例如输入 4,5,1,6,2,7,3,8 这 8 个数字，则最小的 4 个数字是 1,2,3,4。
2 思路
通过 partition 算法确定第 k 小的元素位置 pivot ，此时 pivot 前面的元素都比它小，后面的元素都比它大。因为我们要求最小的 k 个数，所以返回数组中前 k 个元素。
注：这种解法会改动原始数组。
3 代码实现
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> retList = new ArrayList<Integer>();
if(input==null || k>input.length || k<=0){
return retList;
}
int start = 0;
int end = input.length-1;
int pivot = partition(input,start,end);
while(pivot!=k-1){
if(pivot>k-1){
end = pivot-1;
pivot = partition(input,start,end);
}
else{
start = pivot+1;
pivot = partition(input,start,end);
}
}
for(int i=0;i<=pivot;i++){
retList.add(input[i]);
}
return retList;
}
private int partition(int[] input,int start,int end){
int pivot = input[start];
while(start<end){
while(start<end && pivot<=input[end]){
end--;
}
input[start] = input[end];
while(start<end && pivot>=input[start]){
start++;
}
input[end] = input[start];
}
input[start] = pivot;
return start;
}
}