题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
这道题也可以相当于快速排序的一个延伸。
快速排序的核心依然是partition操作。那么我们在成功的进行了一次partition操作之后，第一个元素就被放在了最终排序的位置。它左边的元素都小于它，右边的元素都大于它。
我们可以直接让这个元素的位置的k进行比较，如果和k相等，那么很明显这个元素左边的元素就是最小的k个数。
我们只需要把它左边的元素一次添加到数组中返回就得到了最终答案。
如果p>k，那么很明显我们可以去左边递归地找，如果p<k那么我们可以递归到右边去找。
代码如下:
public int[] getMinKNums(int[] nums,int k,int l,int r){
int p = partition(nums,l,r);
int[] ret = new int[k];
if(p==k-1){
for(int i=0;i<k;i++){
ret[i] = nums[i];
}
return ret;
}else if(p>k-1){
return getMinKNums(nums,k,l,p-1);
}else{
return getMinKNums(nums,k,p+1,r);
}
}
安克创新 Anker公司福利 621人发布
