欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 面试题40. 最小的k个数

程序员文章站 2022-04-05 15:40:54
...

Leetcode 面试题40. 最小的k个数
直接使用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)));
    }
}
相关标签: leetcode解题