<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 0295. 數據流的中位數 ## 題目地址(295. 數據流的中位數) <https://leetcode-cn.com/problems/find-median-from-data-stream/> ## 題目描述 ``` <pre class="calibre18">``` 中位數是有序列表中間的數。如果列表長度是偶數,中位數則是中間兩個數的平均值。 例如, [2,3,4] 的中位數是 3 [2,3] 的中位數是 (2 + 3) / 2 = 2.5 設計一個支持以下兩種操作的數據結構: void addNum(int num) - 從數據流中添加一個整數到數據結構中。 double findMedian() - 返回目前所有元素的中位數。 示例: addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 進階: 如果數據流中所有整數都在 0 到 100 范圍內,你將如何優化你的算法? 如果數據流中 99% 的整數都在 0 到 100 范圍內,你將如何優化你的算法? ``` ``` ## 前置知識 - 堆 - 隊列 ## 公司 - 阿里 - 百度 - 字節 ## 思路 這道題目是求動態數據的中位數,在 leetcode 難度為`hard`. 如果這道題是求靜態數據的中位數,我們用數組去存儲, 空間復雜度 O(1), 時間復雜度 O(1) > 空間復雜度指的是除了存儲數據之外額外開辟的用于計算等任務的內存空間 代碼也比較簡單 ``` <pre class="calibre18">``` <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">findMedian</span>(<span class="hljs-params">a</span>) </span>{ <span class="hljs-keyword">return</span> a.length % <span class="hljs-params">2</span> === <span class="hljs-params">0</span> ? (a[a.length >> <span class="hljs-params">1</span>] + a[a.length >> (<span class="hljs-params">1</span> + <span class="hljs-params">1</span>)]) / <span class="hljs-params">2</span> : a[a.length >> <span class="hljs-params">1</span>]; } ``` ``` 但是題目要求是動態數據, 那么是否可以每次添加數據的時候,都去排一次序呢? 假如我們每次插入都用`快速排序`進行排序的話,那么時間復雜度是 O(nlogn) + O(1) > O(nlogn) 是排序的時間復雜度 O(1)是查詢中位數的時間復雜度 如果你用這種思路進行的話, 恐怕 leetcode 會超時。 那么如何優化呢? 答案是使用堆, Java, C++等語言都有`優先級隊列`中這種數據結構, 優先級隊列本質上就是一個堆。 關于堆和優先級隊列的關系,我會放在《數據結構和算法》部分講解。這里不贅述 如果借助堆這種數據結構, 就可以輕易實現了。 具體的做法是,建立兩個堆,這兩個堆需要滿足: 1. 大頂堆元素都比小頂堆小(由于堆的特點其實只要比較堆頂即可) 2. 大頂堆元素不小于小頂堆,且最多比小頂堆多一個元素 滿足上面兩個條件的話,如果想要找到中位數,就比較簡單了 - 如果兩個堆數量相等(本質是總數為偶數), 就兩個堆頂元素的平均數 - 如果兩個堆數量不相等(本質是總數為奇數), 就取大頂堆的堆頂元素 比如對于\[1,2,3\] 求中位數: ![](https://img.kancloud.cn/ab/9c/ab9ce074ad5a43d9425d85d5d44c450e_828x220.jpg) 再比如對于\[1,2,3, 4\] 求中位數: ![](https://img.kancloud.cn/d6/8d/d68d39b39f00b2f3a6febc0088c97d6e_825x237.jpg) ## 關鍵點解析 - 用兩個堆(一個大頂堆,一個小頂堆)來簡化時間復雜度 - 用優先級隊列簡化操作 > JavaScript 不像 Java, C++等語言都有`優先級隊列`中這種數據結構, 因此大家可以使用社區的實現 個人認為沒有非要糾結于優先級隊列怎么實現, 至少這道題不是考這個的 優先級隊列的實現個人認為已經超過了這道題想考察的范疇 > > ## 代碼 如果不使用現成的`優先級隊列`這種數據結構,代碼可能是這樣的: ``` <pre class="calibre18">``` <span class="hljs-title">/** * initialize your data structure here. */</span> <span class="hljs-keyword">var</span> MedianFinder = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">this</span>.maxHeap = []; <span class="hljs-keyword">this</span>.minHeap = []; }; <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">minHeapify</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">this</span>.minHeap.unshift(<span class="hljs-params">null</span>); <span class="hljs-keyword">const</span> a = <span class="hljs-keyword">this</span>.minHeap; <span class="hljs-title">// 為了方便大家理解,這里選用了粗暴的實現</span> <span class="hljs-title">// 時間復雜度為O(n)</span> <span class="hljs-title">// 其實可以降到O(logn), 具體細節我不想在這里講解和實現</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = a.length - <span class="hljs-params">1</span>; i >> <span class="hljs-params">1</span> > <span class="hljs-params">0</span>; i--) { <span class="hljs-title">// 自下往上堆化</span> <span class="hljs-keyword">if</span> (a[i] < a[i >> <span class="hljs-params">1</span>]) { <span class="hljs-title">// 如果子元素更小,則交換位置</span> <span class="hljs-keyword">const</span> temp = a[i]; <span class="hljs-keyword">this</span>.minHeap[i] = a[i >> <span class="hljs-params">1</span>]; <span class="hljs-keyword">this</span>.minHeap[i >> <span class="hljs-params">1</span>] = temp; } } <span class="hljs-keyword">this</span>.minHeap.shift(<span class="hljs-params">null</span>); } <span class="hljs-function"><span class="hljs-keyword">function</span> <span class="hljs-title">maxHeapify</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">this</span>.maxHeap.unshift(<span class="hljs-params">null</span>); <span class="hljs-keyword">const</span> a = <span class="hljs-keyword">this</span>.maxHeap; <span class="hljs-title">// 為了方便大家理解,這里選用了粗暴的實現</span> <span class="hljs-title">// 時間復雜度為O(n)</span> <span class="hljs-title">// 其實可以降到O(logn), 具體細節我不想在這里講解和實現</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">let</span> i = a.length - <span class="hljs-params">1</span>; i >> <span class="hljs-params">1</span> > <span class="hljs-params">0</span>; i--) { <span class="hljs-title">// 自下往上堆化</span> <span class="hljs-keyword">if</span> (a[i] > a[i >> <span class="hljs-params">1</span>]) { <span class="hljs-title">// 如果子元素更大,則交換位置</span> <span class="hljs-keyword">const</span> temp = a[i]; <span class="hljs-keyword">this</span>.maxHeap[i] = a[i >> <span class="hljs-params">1</span>]; <span class="hljs-keyword">this</span>.maxHeap[i >> <span class="hljs-params">1</span>] = temp; } } <span class="hljs-keyword">this</span>.maxHeap.shift(<span class="hljs-params">null</span>); } <span class="hljs-title">/** * @param {number} num * @return {void} */</span> MedianFinder.prototype.addNum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">num</span>) </span>{ <span class="hljs-title">// 為了大家容易理解,這部分代碼寫的比較冗余</span> <span class="hljs-title">// 插入</span> <span class="hljs-keyword">if</span> (num >= (<span class="hljs-keyword">this</span>.minHeap[<span class="hljs-params">0</span>] || <span class="hljs-params">Number</span>.MIN_VALUE)) { <span class="hljs-keyword">this</span>.minHeap.push(num); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">this</span>.maxHeap.push(num); } <span class="hljs-title">// 調整兩個堆的節點數量平衡</span> <span class="hljs-title">// 使得大頂堆的數量最多大于小頂堆一個, 且一定不小于小頂堆數量</span> <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.maxHeap.length > <span class="hljs-keyword">this</span>.minHeap.length + <span class="hljs-params">1</span>) { <span class="hljs-title">// 大頂堆的堆頂元素移動到小頂堆</span> <span class="hljs-keyword">this</span>.minHeap.push(<span class="hljs-keyword">this</span>.maxHeap.shift()); } <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.minHeap.length > <span class="hljs-keyword">this</span>.maxHeap.length) { <span class="hljs-title">// 小頂堆的堆頂元素移動到大頂堆</span> <span class="hljs-keyword">this</span>.maxHeap.push(<span class="hljs-keyword">this</span>.minHeap.shift()); } <span class="hljs-title">// 調整堆頂元素</span> <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.maxHeap[<span class="hljs-params">0</span>] > <span class="hljs-keyword">this</span>.minHeap[<span class="hljs-params">0</span>]) { <span class="hljs-keyword">const</span> temp = <span class="hljs-keyword">this</span>.maxHeap[<span class="hljs-params">0</span>]; <span class="hljs-keyword">this</span>.maxHeap[<span class="hljs-params">0</span>] = <span class="hljs-keyword">this</span>.minHeap[<span class="hljs-params">0</span>]; <span class="hljs-keyword">this</span>.minHeap[<span class="hljs-params">0</span>] = temp; } <span class="hljs-title">// 堆化</span> maxHeapify.call(<span class="hljs-keyword">this</span>); minHeapify.call(<span class="hljs-keyword">this</span>); }; <span class="hljs-title">/** * @return {number} */</span> MedianFinder.prototype.findMedian = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">if</span> ((<span class="hljs-keyword">this</span>.maxHeap.length + <span class="hljs-keyword">this</span>.minHeap.length) % <span class="hljs-params">2</span> === <span class="hljs-params">0</span>) { <span class="hljs-keyword">return</span> (<span class="hljs-keyword">this</span>.minHeap[<span class="hljs-params">0</span>] + <span class="hljs-keyword">this</span>.maxHeap[<span class="hljs-params">0</span>]) / <span class="hljs-params">2</span>; } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.maxHeap[<span class="hljs-params">0</span>]; } }; <span class="hljs-title">/** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */</span> ``` ``` 其中`minHeapify` 和 `maxHeapify` 的過程都有一個hack操作,就是: ``` <pre class="calibre18">``` <span class="hljs-keyword">this</span>.heap.unshift(<span class="hljs-params">null</span>); <span class="hljs-title">// ....</span> <span class="hljs-keyword">this</span>.heap.shift(<span class="hljs-params">null</span>); ``` ``` 其實就是為了存儲的數據從1開始,這樣方便計算。 即對于下標為i的元素, `i >> 1` 一定是父節點的下標。 ![](https://img.kancloud.cn/59/64/5964ac5fcfb8761562bc3f7150e817d2_835x251.jpg) > 這是因為我用滿二叉樹來存儲的堆 這個實現比較繁瑣,下面介紹一種優雅的方式,假設JS和Java和C++等語言一樣有`PriorityQueue`這種數據結構,那么我們實現就比較簡單了。 代碼: > 關于PriorityQueue的實現,感興趣的可以看下 <https://github.com/janogonzalez/priorityqueuejs> ``` <pre class="calibre18">``` <span class="hljs-keyword">var</span> MedianFinder = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">this</span>.maxHeap = <span class="hljs-keyword">new</span> PriorityQueue((a, b) => a - b); <span class="hljs-keyword">this</span>.minHeap = <span class="hljs-keyword">new</span> PriorityQueue((a, b) => b - a); }; <span class="hljs-title">/** * @param {number} num * @return {void} */</span> MedianFinder.prototype.addNum = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">num</span>) </span>{ <span class="hljs-title">// 我們的目標就是建立兩個堆,一個大頂堆,一個小頂堆</span> <span class="hljs-title">// 結合中位數的特點</span> <span class="hljs-title">// 這兩個堆需要滿足:</span> <span class="hljs-title">// 1. 大頂堆元素都比小頂堆小(由于堆的特點其實只要比較堆頂即可)</span> <span class="hljs-title">// 2. 大頂堆元素不小于小頂堆,且最多比小頂堆多一個元素</span> <span class="hljs-title">// 滿足上面兩個條件的話,如果想要找到中位數,就比較簡單了</span> <span class="hljs-title">// 如果兩個堆數量相等(本質是總數為偶數), 就兩個堆頂元素的平均數</span> <span class="hljs-title">// 如果兩個堆數量不相等(本質是總數為奇數), 就取大頂堆的堆頂元素</span> <span class="hljs-title">// 問題如果保證滿足上述兩個特點</span> <span class="hljs-title">// 1. 保證第一點</span> <span class="hljs-keyword">this</span>.maxHeap.enq(num); <span class="hljs-title">// 由于小頂堆的所有數都來自大頂堆的堆頂元素(最大值)</span> <span class="hljs-title">// 因此可以保證第一點</span> <span class="hljs-keyword">this</span>.minHeap.enq(<span class="hljs-keyword">this</span>.maxHeap.deq()); <span class="hljs-title">// 2. 保證第二點</span> <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.maxHeap.size() < <span class="hljs-keyword">this</span>.minHeap.size()){ <span class="hljs-keyword">this</span>.maxHeap.enq(<span class="hljs-keyword">this</span>.minHeap.deq()); } }; <span class="hljs-title">/** * @return {number} */</span> MedianFinder.prototype.findMedian = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params"></span>) </span>{ <span class="hljs-keyword">if</span> (<span class="hljs-keyword">this</span>.maxHeap.size() == <span class="hljs-keyword">this</span>.minHeap.size()) <span class="hljs-keyword">return</span> (<span class="hljs-keyword">this</span>.maxHeap.peek() + <span class="hljs-keyword">this</span>.minHeap.peek()) / <span class="hljs-params">2.0</span>; <span class="hljs-keyword">else</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">this</span>.maxHeap.peek(); }; <span class="hljs-title">/** * Your MedianFinder object will be instantiated and called as such: * var obj = new MedianFinder() * obj.addNum(num) * var param_2 = obj.findMedian() */</span> ``` ```
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看