Leetcode 面试题40. 最小的k个数
程序员文章站
2022-04-05 15:40:54
...
直接使用API函数调用快速排序,面试种肯定是不行的!
利用快速排序的分区思想,我们知道快排的划分函数每次执行完后都能将数组分成两个部分,小于等于分界值 pivot
的元素的都会被放到数组的左边,大于的都会被放到数组的右边,然后返回分界值的下标pos
。
那么:
如果pos
= k
直接返回pos
<k
对左边再次分区,因为正好第k
大的数一定再左
边,我们要找到它pos
<k
对左边再次分区,因为正好第k
大的数一定再右
边,我们要找到它
import java.util.Arrays;
class Solution {
private int k ;
private int[] arr ;
public int[] getLeastNumbers(int[] arr, int k) {
this.k = k;
this.arr = arr;
if(k != arr.length) {//如果等于length的话不用找了,就是整个数组
quickSort(0, arr.length - 1);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
public void quickSort(int left,int right){
int pos = partition(arr, left, right);
if(pos == k) return;
if(pos < k){
quickSort(pos+1,right);
}else
quickSort(left,pos-1);
}
private int partition(int[] arr , int left , int right){
int base = left;
while(left <= right){
while (left <= right && arr[left] <= arr[base]){
left++;
}
while (left <= right && arr[right] >= arr[base]){
right--;
}
if (left <= right)
swap(arr,left,right);
}
swap(arr,right,base);
return right;
}
private void swap(int[] arr,int a,int b){
int t= arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(new Solution().getLeastNumbers(new int[]{0,0,1,5,4,2,4,3,1,4}, 5)));
}
}