LeetCode如何解決前K個高頻元素問題

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

題目

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

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

示例 2:

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

提示：

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

思路

• 首先遍歷整個數組，并使用哈希表記錄每個數字出現的次數，并形成一個「出現次數數組」。找出原數組的前 kk 個高頻元素，就相當于找出「出現次數數組」的前 kk 大的值。

• 最簡單的做法是給「出現次數數組」排序。但由于可能有 O(N)O(N) 個不同的出現次數（其中 NN 為原數組長度），故總的算法復雜度會達到 O(N\log N)O(NlogN)，不滿足題目的要求。

• 在這里，我們可以利用堆的思想：建立一個小頂堆，然后遍歷「出現次數數組」：

• 如果堆的元素個數小于 kk，就可以直接插入堆中。

• 如果堆的元素個數等于 kk，則檢查堆頂與當前出現次數的大小。如果堆頂更大，說明至少有 kk 個數字的

• 出現次數比當前值大，故舍棄當前值；否則，就彈出堆頂，并將當前值插入堆中。

• 遍歷完成后，堆中的元素就代表了「出現次數數組」中前 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;
    }
}

感謝你能夠認真閱讀完這篇文章，希望小編分享的“LeetCode如何解決前K個高頻元素問題”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!