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

[40]最小的k个数

程序员文章站 2024-01-22 11:20:10
...


链接

题目描述

[40]最小的k个数

1.经典 top k 问题

(1)快排:最最最高效解决top k 问题—O(N)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k == 0 || arr.length == 0){
            return new int[0];
        }
        //查找下标是k-1的数
        return quickSearch(arr,0,arr.length-1,k-1);
    }
    
    private int[] quickSearch(int[] arr,int lo,int hi,int k){
        int j = partition(arr,lo,hi);
        if(j == k){
            return Arrays.copyOf(arr,j+1);
        }
        return j > k ? quickSearch(arr,lo,j-1,k) : quickSearch(arr,j+1,hi,k); 
    }
    
    private int partition(int[] arr,int l ,int r){
        int less = l - 1;
        int more = r;
        while(l < more){
            if(arr[l] < arr[r]){
                swap(arr,++less,l++);
            }else if(arr[l] > arr[r]){
                swap(arr,--more,l);
            }else{
                l++;
            }
        }
        swap(arr,r,more);
        return more;
    }
    
    private void swap(int[] arr,int i , int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
}

[40]最小的k个数

(2)大根堆(前k小)/小根堆(前k大),Java中有现成的PriorityQueue,实现起来最简单,O(NlogK)

(3)二叉搜索树也可以O(NlogK)解决Top K问题

2.自己做法(Arrays.sort())

直接对数组排序,然后找出前 k 个数就是最小的数。
排序时间复杂度 : O(nlogn)

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);
        int[] res = new int[k];
        for(int i = 0; i < k ; i++){
            res[i] = arr[i];
        }
        return res;
    }
}
相关标签: leetcode每日一题