前言：優(yōu)先隊(duì)列底層是由大根堆或小根堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的。

前K個(gè)高頻元素

347.?前 K 個(gè)高頻元素

給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，請(qǐng)你返回其中出現(xiàn)頻率前?k?高的元素。你可以按?任意順序?返回答案。

示例 1:

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

示例 2:

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

題目解讀：題目的要求是要我們找出在一個(gè)數(shù)組中找出k個(gè)出現(xiàn)頻率最多的元素。

剛看到這個(gè)題目時(shí)候，直接冒出一個(gè)解決思路，就是利用桶排序的思想，?定義一個(gè)很大長(zhǎng)度的數(shù)組，數(shù)組哪個(gè)位置有數(shù)，那就在哪個(gè)下標(biāo)所在位置加一，然后排序，取出前k個(gè)最大值。

但是，如果利用這種思想來(lái)做題，直接大大浪費(fèi)了很多的空間，還有一些沒有必要的時(shí)間。

所有就引出了哈希表這個(gè)數(shù)據(jù)結(jié)構(gòu)。我們可以把數(shù)組中出現(xiàn)的元素值作為哈希表的key值，然后出現(xiàn)的頻率作為它的value，在遍歷一遍數(shù)組之后，哈希表已經(jīng)存儲(chǔ)完畢了，再將哈希表進(jìn)行排序，就可以得到前k個(gè)最大元素了。

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ak = new int[k];
        int cnt = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        // 根據(jù)哈希表的Value值進(jìn)行的排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Map.Entry.comparingByValue(Comparator.reverseOrder()));

        for (int i = 0; i < k; i++) {
            ak[cnt++] = list.get(i).getKey();
        }

        return ak;
    }
}

雖說這樣就可以做完了，但是它的時(shí)間復(fù)雜度是O（n*k），我們并不滿足如此，如果使用優(yōu)先隊(duì)列，我們就可以將時(shí)間復(fù)雜度減少到O（n*logk)。如果k越大，兩者時(shí)間復(fù)雜度還會(huì)更大。

大根堆其實(shí)是一顆二叉樹，是一顆二叉平衡樹，它的根結(jié)點(diǎn)就是最大的數(shù)，左邊結(jié)點(diǎn)會(huì)小于右邊結(jié)點(diǎn)。

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ak = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        //這里是大頂堆
        // PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);

        //小根堆
         PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0) +1);   //default
           
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            // pq.add(new int[]{entry.getKey(),entry.getValue()});
              if(pq.size()<k){//小頂堆元素個(gè)數(shù)小于k個(gè)時(shí)直接加
                pq.add(new int[]{entry.getKey(),entry.getValue()});
            }else{
                if(entry.getValue()>pq.peek()[1]){
                    //當(dāng)前元素出現(xiàn)次數(shù)大于小頂堆的根結(jié)點(diǎn)(這k個(gè)元素中出現(xiàn)次數(shù)最少的那個(gè))
                    pq.poll();
                    //彈出隊(duì)頭(小頂堆的根結(jié)點(diǎn)),即把堆里出現(xiàn)次數(shù)最少的那個(gè)刪除,留下的就是出現(xiàn)次數(shù)多的了
                    pq.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }
        for(int i =k-1;i >=0 ;i--){
            ak[i] = pq.poll()[0];
        }

        return ak;
    }
}

滑動(dòng)窗口最大值

239.?滑動(dòng)窗口最大值

給你一個(gè)整數(shù)數(shù)組?nums，有一個(gè)大小為?k?的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的?k?個(gè)數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。

返回?滑動(dòng)窗口中的最大值?。

示例 1：

輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3
輸出：[3,3,5,5,6,7]
解釋：
滑動(dòng)窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

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

?如果做完第一題，直接來(lái)做第二題的，肯定第一秒想到的是直接使用循環(huán)＋大根堆來(lái)實(shí)現(xiàn)，那真的能實(shí)現(xiàn)嗎？we can try

?

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int cnt = 0;
        int len = nums.length;
        int[] ans = new int[len - k +1 ];
        for(int i=0;i <= len-k;i++){
            PriorityQueue<Integer> pq = new PriorityQueue(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
            });;
            for(int j = i;j < i+k ; j++)
                pq.add(nums[j]);

            ans[cnt++] = pq.poll();
        }
        return ans;
    }
}

直接一整個(gè)時(shí)間超限了。

那這個(gè)題目要怎么來(lái)做呢？

class myQueue{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int val){
        if(!deque.isEmpty() && deque.peek() == val)
            deque.poll();
    }

    void add(int val){
        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();
        }
        deque.add(val);
    }

    int peek(){
        return deque.peek();
    }

}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
          if (nums.length == 1) {
            return nums;
        }
        int len = nums.length - k + 1;
        //存放結(jié)果元素的數(shù)組
        int[] res = new int[len];
        int cnt = 0;

        myQueue myQueue = new myQueue();
        //先將前k的元素放入隊(duì)列
        for (int i = 0; i < k; i++) {
            myQueue.add(nums[i]);
        }
        res[cnt++] = myQueue.peek();
        for (int i = k; i < nums.length; i++) {
            //滑動(dòng)窗口移除最前面的元素，移除是判斷該元素是否放入隊(duì)列
            myQueue.poll(nums[i - k]);
            //滑動(dòng)窗口加入最后面的元素
            myQueue.add(nums[i]);
            //記錄對(duì)應(yīng)的最大值
            res[cnt++] = myQueue.peek();
        }
        return res;
    }
}

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-744803.html

到了這里，關(guān)于力扣刷題之優(yōu)先隊(duì)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！