LeetCode-面试题40-最小的k个数

排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)
            return new int[0];
        if(k>=arr.length)
            return arr;
        Arrays.sort(arr);
        return Arrays.copyOf(arr,k);
    }
}

计数排序

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)
            return new int[0];
        if(k>=arr.length)
            return arr;
        int[] count=new int[10000];
        for(int a:arr){
          count[a]++;  
        }
        int[] res=new int[k];
        int i=0;
        int j=0;
        while(k>0){
            if(count[i]>0){
                count[i]--;
                res[j]=i;
                j++;
                k--;
            }else{
                i++;
            }
        }
        return res;
    }
}

使用容量为k的大顶堆

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)
            return new int[0];
        if(k>=arr.length)
            return arr;
        Queue<Integer> q=new PriorityQueue<>((a,b)->b-a);
        // Queue<Integer> q=new PriorityQueue<>(new Comparator<Integer>(){
        //     public int compare(Integer a,Integer b){
        //         return b.compareTo(a);
        //     }
        // });
        for(int a:arr){
            if(k>q.size()){
                q.offer(a);
            }else{
                if(a<q.peek()){
                    q.poll();
                    q.offer(a);
                }
            }
        }
        int[] res=new int[k];
        int index=0;
        for(int i:q){
            res[index++]=i;
        }
        return res;
    }
}

利用快排思想

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0)
            return new int[0];
        if(k>=arr.length)
            return arr;
        int left=0;
        int right=arr.length-1;
        int index=quickSort(arr,k,left,right);
        int[] res=new int[k];
        for(int i=0;i<k;i++){
            res[i]=arr[i];
        }
        return res;
    }
    public int quickSort(int[] arr,int k,int left,int right){
        // 注意记录原有值
        int i=left;
        int j=right;
        // 快排部分
        int p=arr[left];
        while(left<right){
            while(right>left&&arr[right]>p){
                right--;
            }
            arr[left]=arr[right];
            while(left<right&&arr[left]<=p){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=p;
        // 递归部分，当k=left+1时，left左边部分就为最小的k个数
        if(left+1==k)
            return left;
        else if(left+1<k){
            return quickSort(arr,k,left+1,j);
        }else{
            return quickSort(arr,k,i,left-1);
        }
    }
}

时间复杂度

O(nlogk)