文章目錄

• 題目描述
• • • 知識點
    • • • 1. 優先隊列
        • 2. Java 中 queue 的 offer、poll 等區別
• 思路 && 代碼
• • • 二刷

打卡第十一天～

題目描述

• 雖然但是，這是一道很nice的題目（涉及的知識點、運用很實用，見知識點模塊）
  
  

知識點

1. 優先隊列

• priorityQueue 是 Queue 接口的實現，可以對其中元素進行排序。
• 默認順序是升序；采用的是堆排序（小頂堆），因此只能保證根是最值，整個堆并不是有序的。
• 自定義比較類：在 priorityQueue 的構造函數參數中用 Lambda 表達式表示即可。

2. Java 中 queue 的 offer、poll 等區別

• add、offer：都是添加；隊滿情況 add 拋出異常，而 offer 則返回 false，可用于判斷
• remove、poll：都是刪除首元素；隊空情況remove拋出異常，而 poll 返回 null
• element、peek：都是查詢首元素；隊空情況element拋出異常，而peek 返回 null

思路 && 代碼

• 代碼量不大，主要考察的思路～
• 首先中位數需要考慮總數奇偶情況：奇取中值，偶取平均值。
• 然后既然想獲得好的時間復雜度，那就空間換時間了（否則數組慢慢來也行了）
• 接著，既然中位數是在排序后元素集的中間，那么我們可以有這么一個考慮：中間靠兩個數據結構實現（畢竟一半一半嘛！），而有序（或局部有序）的數據結構中，進行 add 操作的時間復雜度最低的(O(logn))就是堆了！
• 因此，我們選取優先隊列來作為實現的數據結構～
• 主要思路：大頂堆存儲較小部分，小頂堆存儲較大部分。通過兩個堆的堆頂來取中位數。通過先添加到堆a，再添加堆a的堆頂到堆b的“洗元素”方式來維護較大、較小的屬性。

class MedianFinder {Queue<Integer> smallHeap, bigHeap;/** initialize your data structure here. */public MedianFinder() {// 各存一半：small 小頂堆存儲較大部分；big 大頂堆存儲較小部分smallHeap = new PriorityQueue<>();bigHeap = new PriorityQueue<>((x, y) -> (y - x));}// 維護兩個 Heap 的較大、較小屬性：O(logn)public void addNum(int num) {// N = 奇數：增加 bigHeap 元素，通過先添加到 smallHeap，再獲取其堆頂實現if(smallHeap.size() != bigHeap.size()) {smallHeap.add(num);bigHeap.add(smallHeap.poll());} // N = 偶數：增加 small 元素，通過先添加到 bigHeap，再獲取其堆頂實現else {bigHeap.add(num);smallHeap.add(bigHeap.poll());}}// O(1)public double findMedian() {// 偶數情況if(smallHeap.size() == bigHeap.size()) {// 較大堆的最小值 + 較小堆里的最大值return (smallHeap.peek() + bigHeap.peek()) / 2.0;}// 奇數情況else {return smallHeap.peek();}} }/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj = new MedianFinder();* obj.addNum(num);* double param_2 = obj.findMedian();*/

二刷

• 關鍵詞：優先隊列、堆之間洗數據、Lambda 表達式
• 思路還是難忘，代碼也不多。這道題保持 hard 的時間估計不長了…

class MedianFinder {Queue<Integer> smallTop = new PriorityQueue<>();Queue<Integer> bigTop = new PriorityQueue<>((x, y) -> (y - x));public MedianFinder() {}public void addNum(int num) {if(smallTop.size() == bigTop.size()) {bigTop.add(num);smallTop.add(bigTop.poll());}else {smallTop.add(num);bigTop.add(smallTop.poll());}}public double findMedian() {if(smallTop.size() == bigTop.size()) {return (smallTop.peek() + bigTop.peek()) / 2.0;}else {return smallTop.peek();}} }

總結

以上是生活随笔為你收集整理的【LeetCode笔记】剑指Offer 41. 数据流中的中位数（Java、堆、优先队列、知识点）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。