利用快排的类二叉排序数的思想解决问题
最小的K个数
http://www.nowcoder.com/questionTerminal/6a296eb82cf844ca8539b57c23e6e9bf
思路：
首先我们要明确，这道题并不是考验对排序的掌握，而是要通过一个容量为k的数据结构将整个数组最小的k个数放进去排序好然后再返回。快排思路：
我们都知道，快排是以第一位数字为基准数字，然后将它放在合适的位置上以满足左边的数字都小于他，右边的数字都大于他，那么就产生了一个思路 如果我们快排一轮结束后，给该数字确定的位置正好等于k的时候，那我们包括该数字在内，是不是正好返回当前位置之前的数组排序返回即可。 所以我们就可以每次快排后返回第一位最终的数组下标来判断是否满足条件，以下见代码： ```/*
*获取基准值，然后判断是否符合标准，是的话获取范围内的数组值并且排序返回*/
public ArrayList<Integer> quick_search(int[] input, int left, int right, int k){
//获取基准值下标
int index = quick_sort(left,right,input);
if(index == k){
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0;i < index+1;i++){
list.add(input[i]);
}
Collections.sort(list);
return list;
}
//若是index不满足该条件，则考虑是在当前下标左边还是右边，然后继续开启遍历
return index > k ? quick_search(input,left,index-1,k) : quick_search(input,index+1,right,k);
}
/*
*返回一轮快排结束后的基准值下标
*/
public int quick_sort(int left,int right,int[] input){
int l = left,r = right;
int key = input[left];
while (l < r){
while(input[r] >= key && l < r)r--;
while(input[l] <= key && l < r)l++;
if(l < r){
int temp = input[r];
input[r] = input[l];
input[l] = temp;
}
}
input[left] = input[l];
input[l] = key;
return l;
}**主程序：欢迎指正错误~^^**
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
//数组为空，k值为0，k值超出范围，都会返回空list
if(input == null || k == 0 || input.length == 0 || k > input.length)return new ArrayList<Integer>();
//进入快排寻找
return quick_search(input,0,input.length-1,k-1);
}```
，我是应该不会去，三面直接拒绝不面了
查看7道真题和解析