快捷導(dǎo)航

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

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

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

題目描述：

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

示例：

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

思路：

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

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

整體排序

整體建立一個(gè)大小為N的小根堆

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

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

整體建立一個(gè)大小為N的小根堆

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

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會(huì)默認(rèn)成為小根堆，然后再把前k個(gè)元素放到ret數(shù)字里即可。

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

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

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

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

class IntCmp implements Comparator<Integer> {

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

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

其中的過(guò)程大概如上圖所示。

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;
    }
}

完整代碼

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

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

第二種方法，通過(guò)大根堆實(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;
    }
}

總結(jié)

到此這篇關(guān)于Java刷題之最小k個(gè)數(shù)的思路及具體實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java算法題最小k個(gè)數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: