快捷導(dǎo)航

Java刷題之最小k個數(shù)的思路及具體實(shí)現(xiàn)

更新時間：2024年10月08日 10:56:07 作者：小川_wenxun

這篇文章主要介紹了Java刷題之最小k個數(shù)的思路及具體實(shí)現(xiàn),最小K個數(shù)是一個經(jīng)典的top-K問題,可以通過整體排序、建立小根堆或大根堆的方式解決,排序方式時間復(fù)雜度較高,適合數(shù)據(jù)量小的場景,小根堆適合k較小的情況,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下

題目描述：

設(shè)計(jì)一個算法，找出數(shù)組中最小的k個數(shù)。以任意順序返回這k個數(shù)均可。

示例：

<strong>輸入：</strong> arr = [1,3,5,7,2,4,6,8], k = 4
<strong>輸出：</strong> [1,2,3,4]

思路：

這個問題屬于是一類問題中，即top-K問題：N個數(shù)據(jù)中，前k個最大/最小的元素，一般來說k比較??；或者是需要找到這組數(shù)據(jù)中第k大/第k小的數(shù)據(jù)。

根據(jù)這道的要求，我們可以有以下三種思路：

整體排序

整體建立一個大小為N的小根堆

把前K個元素創(chuàng)建為大根堆，遍歷剩下的N-K個元素，和堆頂元素比較，如果比堆頂元素學(xué)校，則堆頂元素刪除，但前元素入堆

具體實(shí)現(xiàn)

整體建立一個大小為N的小根堆

通過創(chuàng)建一個小根堆，把要全部元素都放進(jìn)去，然后再把前k個元素提出來即可。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i = 0; i < arr.length; i++){
            priorityQueue.offer(arr[i]);
        }

        int[] ret = new int[k];
        for(int i = 0; i < k; i++){
            ret[i] = priorityQueue.poll();
        }

        return ret;
    }
}

由PriorityQueue創(chuàng)建的堆默認(rèn)為小根堆，所以把元素直接放進(jìn)去，priorityQueue會默認(rèn)成為小根堆，然后再把前k個元素放到ret數(shù)字里即可。

通過大根堆實(shí)現(xiàn)

這里有一個要做的地方：讓PriorityQueue可以實(shí)現(xiàn)大根堆。

通過按住Crtl 鼠標(biāo)點(diǎn)擊 PriorityQueue 可以看到其中實(shí)現(xiàn)的方法，再Crtl 鼠標(biāo)點(diǎn)擊 Comparator，看Comparator接口中的方法，

可以看到其中有個 compare方法，這便是通過比較 o1，o2的值來進(jìn)行小根堆的實(shí)現(xiàn)，這里我們可以通過重寫compare方法來實(shí)現(xiàn)大根堆。這里選擇的是創(chuàng)建一個新類來實(shí)現(xiàn)。

class IntCmp implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

然后把前K個元素放進(jìn)大根堆，如果根節(jié)點(diǎn)的值大于可能要放進(jìn)來的值，則把根節(jié)點(diǎn)刪除，把該值放進(jìn)來，同時PriorityQueue會保證該堆一直為大根堆。最后遍歷完N-K個值后，再把這些值返回出去。

其中的過程大概如上圖所示。

class Solution{
    public int[] smallestK(int[] arr, int k) {
    int[] ret = new int[k];
    if(arr == null || k == 0) return ret;
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());

    for (int i = 0; i < k; i++) {
        priorityQueue.offer(arr[i]);
    }

    for (int i =k; i < arr.length; i++) {
        int peekVal = priorityQueue.peek();
        if(peekVal > arr[i]) {
            priorityQueue.peek();
            priorityQueue.offer(arr[i]);
        }
    }

    for (int i = 0; i < k; i++) {
        ret[i] = priorityQueue.poll();
    }
    return ret;
    }
}

完整代碼

第一種方法，通過小根堆實(shí)現(xiàn)

//時間復(fù)雜度為：O((k+1)logN)
class Solution {
    public int[] smallestK(int[] arr, int k) {
                PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //時間復(fù)雜度為O(N*logN)
        for (int i = 0; i < arr.length; i++) {
            priorityQueue.offer(arr[i]);
        }
        
        //時間復(fù)雜度為O(K*logN)
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        
        return ret;
    }
}

第二種方法，通過大根堆實(shí)現(xiàn)

class IntCmp implements Comparator<Integer> {

    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

class Solution{
    public int[] smallestK(int[] arr, int k) {
    int[] ret = new int[k];
    if(arr == null || k == 0) return ret;
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new IntCmp());

    for (int i = 0; i < k; i++) {
        priorityQueue.offer(arr[i]);
    }

    for (int i =k; i < arr.length; i++) {
        int peekVal = priorityQueue.peek();
        if(peekVal > arr[i]) {
            priorityQueue.peek();
            priorityQueue.offer(arr[i]);
        }
    }

    for (int i = 0; i < k; i++) {
        ret[i] = priorityQueue.poll();
    }
    return ret;
    }
}