LeetCode如何解決前K個(gè)高頻元素問(wèn)題

這篇文章主要介紹了LeetCode如何解決前K個(gè)高頻元素問(wèn)題，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

題目

給定一個(gè)非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

提示：

你可以假設(shè)給定的 k 總是合理的，且 1 ≤ k ≤ 數(shù)組中不相同的元素的個(gè)數(shù)。
你的算法的時(shí)間復(fù)雜度必須優(yōu)于 O(n log n) , n 是數(shù)組的大小。
題目數(shù)據(jù)保證答案唯一，換句話說(shuō)，數(shù)組中前 k 個(gè)高頻元素的集合是唯一的。
你可以按任意順序返回答案。

思路

• 首先遍歷整個(gè)數(shù)組，并使用哈希表記錄每個(gè)數(shù)字出現(xiàn)的次數(shù)，并形成一個(gè)「出現(xiàn)次數(shù)數(shù)組」。找出原數(shù)組的前 kk 個(gè)高頻元素，就相當(dāng)于找出「出現(xiàn)次數(shù)數(shù)組」的前 kk 大的值。

• 最簡(jiǎn)單的做法是給「出現(xiàn)次數(shù)數(shù)組」排序。但由于可能有 O(N)O(N) 個(gè)不同的出現(xiàn)次數(shù)（其中 NN 為原數(shù)組長(zhǎng)度），故總的算法復(fù)雜度會(huì)達(dá)到 O(N\log N)O(NlogN)，不滿足題目的要求。

• 在這里，我們可以利用堆的思想：建立一個(gè)小頂堆，然后遍歷「出現(xiàn)次數(shù)數(shù)組」：

• 如果堆的元素個(gè)數(shù)小于 kk，就可以直接插入堆中。

• 如果堆的元素個(gè)數(shù)等于 kk，則檢查堆頂與當(dāng)前出現(xiàn)次數(shù)的大小。如果堆頂更大，說(shuō)明至少有 kk 個(gè)數(shù)字的

• 出現(xiàn)次數(shù)比當(dāng)前值大，故舍棄當(dāng)前值；否則，就彈出堆頂，并將當(dāng)前值插入堆中。

• 遍歷完成后，堆中的元素就代表了「出現(xiàn)次數(shù)數(shù)組」中前 kk 大的值

代碼

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> occ = new HashMap<Integer,Integer>();
        for (int num : nums) {
            occ.put(num,occ.getOrDefault(num,0)+1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (Map.Entry<Integer, Integer> integerIntegerEntry : occ.entrySet()) {
            int num = integerIntegerEntry.getKey();
            int count = integerIntegerEntry.getValue();
            if(queue.size() == k){
                if(queue.peek()[1] < count){
                    queue.poll();
                    queue.offer(new int[]{num,count});
                }
            }else {
                queue.offer(new int[]{num,count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“LeetCode如何解決前K個(gè)高頻元素問(wèn)題”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!