分为4类解法,重点在后两个解法(快排变种与维持一个大顶堆)

最小的k个数

image.png

class Solution {
    // public int[] getLeastNumbers(int[] arr, int k) {
        //方法一:原生排序
        // Arrays.sort(arr);
        // int[] vect =new int[k];
        // for(int i=0;i<k;i++){
        //     vect[i]=arr[i];
        // }
        // return vect;

        //方法二:选择排序只排前k个,时间复杂度为O(n*k)
    //    for(int i=0;i<k;i++){
    //        int temp = i;
    //        for(int j=i+1;j<arr.length;j++){
    //         if(arr[j]<arr[temp])
    //         temp = j;
    //        }
    //        int t=arr[i];
    //        arr[i]=arr[temp];
    //        arr[temp]=t;
    //    }
    //     int[] vect =new int[k];
    //     for(int i=0;i<k;i++){
    //         vect[i]=arr[i];
    //     }
    //     return vect;
    // //方法三:快速排序(只排半边):是最有效的方法,时间复杂度为O(n)
    //  public int[] getLeastNumbers(int[] arr, int k) {
    //      if(arr.length==0||k==0)return new int[0];
    //      quickSort(arr,0,arr.length-1,k);
    //      return Arrays.copyOf(arr,k);
    // }
    // void quickSort(int[] arr,int start,int end,int k){
    //    if(start<end){//此处不加这个if条件会报错
    //     int index = getIndex(arr,start,end);
    //      if(index==k)return;
    //       if(index<k)quickSort(arr,index+1,end,k);
    //       else quickSort(arr,start,index-1,k);
    //     }
    // }
    // int getIndex(int[] arr,int start,int end){
    //     int temp = arr[start];
    //     int low = start;
    //     int high = end;
    //     while(low<high){
    //         while(arr[high]>=temp&&high>low)high--;
    //         arr[low]=arr[high];
    //         while(arr[low]<=temp&&low<high)low++;
    //         arr[high]=arr[low];
    //     }    
    //     arr[low]=temp;
    //     return low;
    // //     }
    // // 方法四:维持一个大顶堆,时间复杂度为O(NlogK),java默认为小顶堆,需要重写比较器
    // public int[] getLeastNumbers(int[] arr, int k) {
    //     if(arr.length==0||k==0)return new int[0];
    //     Queue<Integer> pq = new PriorityQueue<>((v1,v2)->v2-v1);
    //     for(int i =0;i<arr.length;i++){
    //         if(pq.size()<k){
    //             pq.offer(arr[i]);
    //          }else if(pq.peek()>arr[i]){
    //             pq.poll();
    //             pq.offer(arr[i]);
    //         }
    //     }
    //     int[]  res = new int[k];
    //     int j=0;
    //     for(int num:pq){
    //         res[j++]=num;
    //     }
    //     return res;

    // }
}

这里涉及到快排与堆排的优劣分析,看上去快排在时间与空间复杂度上都比堆排快。
但是如果:第一,算法需要修改原数组,如果原数组不能修改的话,还需要拷贝一份数组,空间复杂度就上去了。

第二,算法需要保存所有的数据。如果把数据看成输入流的话,使用堆的方法是来一个处理一个,不需要保存数据,只需要保存 k 个元素的最大堆。而快速选择的方法需要先保存下来所有的数据,再运行算法。当数据量非常大的时候,甚至内存都放不下的时候,就麻烦了。所以当数据量大的时候还是用基于堆的方法比较好。

LeeCode 215题 数组中第k个最大元素

总共提交了三次,从前往后依次采用快排,最小堆,快排改进(每次选取一个随机数)。快排序要注意主函数中传入quickSort的参数应该是nums.length-k.
image.png

class Solution {
    Random random = new Random();
    void swap(int[] nums,int i,int j){
        int t = nums[i];
        nums[i]= nums[j];
        nums[j] = t;
    }
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums,0,nums.length-1,nums.length-k);
        return nums[nums.length-k];
    }
    void quickSort(int[] nums,int start,int end,int k){
        if(start<end){
        int index = getIndex(nums,start,end);
        if(index==k)return;
        if(index<k) quickSort(nums,index+1,end,k);
        else quickSort(nums,start,index-1,k);
        }
    }
    int getIndex(int[] nums,int start,int end){
        int ran = start + random.nextInt(end-start);
        swap(nums,ran,start);
        int low = start;
        int high =end;
        int temp = nums[start];
        while(low<high){
            while(low<high&&nums[high]>=temp)high--;
            nums[low]=nums[high];
            while(low<high&&nums[low]<=temp)low++;
            nums[high]=nums[low];
        }
        nums[low]=temp;
        return low;
    }
    //小顶堆
    //  public int findKthLargest(int[] nums, int k) {
    //      Queue<Integer> pq = new PriorityQueue<>();
    //      for(int num:nums){
    //          if(pq.size()<k){
    //              pq.offer(num);
                
    //          }else if(num>pq.peek()){
    //              pq.poll();
    //              pq.offer(num);
    //          }
    //      }
    //      return pq.peek();
 
    //  }
}

Q.E.D.