時間復雜度分析：為什么你的中位數查找方案會超時？

分析你提供的MedianFinder實現，其時間復雜度較高的原因主要在于findMedian函數的實現方式。讓我詳細解釋：

代碼時間復雜度分析

你的代碼中兩個主要函數的時間復雜度如下：

1. addNum函數：

   void addNum(int num) {nums.emplace_back(num);
   }
   

   • 時間復雜度：O(1)
   • 解釋：將數字添加到vector末尾，是常數時間操作

2. findMedian函數：

   double findMedian() {if (nums.size() <= 0) {return 0.0;}sort(nums.begin(), nums.end()); // 關鍵性能瓶頸auto n = nums.size();if (n % 2) {return nums[n / 2];} else {return (nums[n / 2] + nums[(n - 1) / 2]) / 2.0;}
   }
   

   • 時間復雜度：O(n log n)，其中n是當前數字的個數
   • 解釋：每次查找中位數時都對整個數組進行排序，排序的時間復雜度是O(n log n)

為什么這個時間復雜度無法通過？

LeetCode 295題「尋找中位數」的測試用例通常包含大量操作。假設：

• 進行m次addNum操作和m次findMedian操作
• 你的實現總時間復雜度為O(m * n log n)，其中n是數據規模

當m和n較大時（例如10^5次操作），這樣的復雜度會導致超時。具體來說：

• 對于10^5次操作，O(n log n)的復雜度意味著約10^5 * 10^5 log 10^5 ≈ 10^{10次操作，這遠遠超過了LeetCode的時間限制（通常要求算法在10}8次操作內完成）

優化方案：使用雙堆實現

為了將時間復雜度優化到更高效的水平，我們可以使用兩個堆（大頂堆和小頂堆）來維護數據：

• 大頂堆maxHeap保存較小的一半數字
• 小頂堆minHeap保存較大的一半數字
• 確保兩個堆的大小差不超過1，這樣堆頂元素就是中位數

class MedianFinder {
private:priority_queue<int> maxHeap; // 大頂堆，保存較小的一半數字priority_queue<int, vector<int>, greater<int>> minHeap; // 小頂堆，保存較大的一半數字public:MedianFinder() {}void addNum(int num) {// 平衡兩個堆的大小if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}// 調整堆的大小，使兩個堆的大小差不超過1if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.top();} else {return (maxHeap.top() + minHeap.top()) / 2.0;}}
};

優化后時間復雜度分析

• addNum函數：O(log n)

  • 堆的插入和彈出操作都是O(log n)
  • 每次添加數字后最多進行一次堆調整

• findMedian函數：O(1)

  • 直接返回堆頂元素，無需排序

空間復雜度

• O(n)，其中n是存儲的數字個數
• 需要兩個堆來存儲數據

這種雙堆實現能夠高效處理大量的添加和查詢操作，輕松通過LeetCode的時間限制。關鍵在于避免了每次查詢都進行排序，而是通過堆結構維護數據的有序性。

在C++中，小頂堆（最小堆）的確可以通過std::priority_queue結合std::greater<int>來實現。下面詳細解釋其原理和用法：

一、小頂堆與greater<int>的關系

1. 堆的基本概念

• 堆是一種完全二叉樹，分為兩種：
  • 大頂堆：每個節點的值都大于或等于其子節點的值，堆頂是最大值。
  • 小頂堆：每個節點的值都小于或等于其子節點的值，堆頂是最小值。

2. std::priority_queue的模板參數

std::priority_queue的默認實現是大頂堆，其模板定義為：

template <class T,class Container = vector<T>,class Compare = less<T>
> class priority_queue;

• T：元素類型。
• Container：存儲元素的容器（默認用vector）。
• Compare：比較函數（默認用less<T>，即大頂堆）。

3. 小頂堆的實現

將Compare參數改為greater<T>即可實現小頂堆：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

• greater<int>是一個函數對象，用于比較兩個整數，當a > b時返回true，因此堆會按升序排列，堆頂是最小值。

二、大頂堆與小頂堆的對比

特性	大頂堆（默認）	小頂堆（greater）
模板參數	priority_queue<int>	priority_queue<int, vector<int>, greater<int>>
堆頂元素	最大值	最小值
插入操作	保持堆頂為最大值	保持堆頂為最小值
應用場景	取最大值、任務調度（高優先級）	取最小值、最小生成樹算法

三、小頂堆的常用操作示例

#include <iostream>
#include <queue>
#include <vector>int main() {// 創建小頂堆std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;// 插入元素minHeap.push(5);minHeap.push(1);minHeap.push(3);minHeap.push(2);minHeap.push(4);// 堆頂是最小值std::cout << "堆頂元素（最小值）: " << minHeap.top() << std::endl;  // 輸出: 1// 彈出堆頂元素minHeap.pop();std::cout << "彈出后堆頂元素: " << minHeap.top() << std::endl;     // 輸出: 2// 查看堆的大小std::cout << "堆大小: " << minHeap.size() << std::endl;            // 輸出: 4// 注意：priority_queue不支持隨機訪問，只能通過彈出操作遍歷while (!minHeap.empty()) {std::cout << minHeap.top() << " ";minHeap.pop();}// 輸出: 2 3 4 5std::cout << std::endl;return 0;
}

四、在中位數查找中的應用

在LeetCode 295題中，小頂堆用于保存較大的一半數字，大頂堆保存較小的一半數字：

class MedianFinder {
private:std::priority_queue<int> maxHeap;          // 大頂堆，保存較小的一半std::priority_queue<int, vector<int>, greater<int>> minHeap;  // 小頂堆，保存較大的一半public:void addNum(int num) {if (maxHeap.empty() || num <= maxHeap.top()) {maxHeap.push(num);} else {minHeap.push(num);}// 調整堆大小平衡if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}double findMedian() {if (maxHeap.size() > minHeap.size()) {return maxHeap.top();} else {return (maxHeap.top() + minHeap.top()) / 2.0;}}
};

• 小頂堆的作用：確保較大的一半數字按升序排列，堆頂是其中最小值。
• 大頂堆的作用：確保較小的一半數字按降序排列，堆頂是其中最大值。

五、greater<int>的底層實現

std::greater<int>是一個函數對象（仿函數），其operator()定義如下：

struct greater {bool operator()(const int& x, const int& y) const {return x > y;}
};

• 當x > y時返回true，因此在priority_queue中，較小的元素會被推到堆頂，形成小頂堆。

總結

• 小頂堆的實現：使用priority_queue<int, vector<int>, greater<int>>。
• 核心原理：通過greater<int>改變元素的比較方式，使堆頂始終為最小值。
• 應用場景：需要頻繁獲取最小值的場景，如優先隊列、中位數查找、最小生成樹算法等。

掌握小頂堆的實現和原理，能幫助你在算法題中高效解決需要維護有序數據的數據結構問題。

雙堆實現中位數查找時堆平衡條件的解釋

在使用雙堆（大頂堆和小頂堆）實現中位數查找器時，堆平衡條件的設計是確保能正確獲取中位數的關鍵。讓我解釋為什么在判斷堆大小時，兩個條件存在差異：

雙堆實現的基本原理

在中位數查找器中，我們使用：

• 大頂堆 maxHeap 保存較小的一半數字
• 小頂堆 minHeap 保存較大的一半數字

為了確保能正確獲取中位數，需要滿足：

• 當總數字個數為奇數時，大頂堆的大小比小頂堆大1，此時大頂堆頂就是中位數
• 當總數字個數為偶數時，兩個堆大小相等，此時中位數是兩個堆頂的平均值

堆平衡條件分析

if (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();
}

為什么大頂堆的條件是 maxHeap.size() > minHeap.size() + 1？

• 大頂堆應該保存較小的一半數字，當總數字個數為奇數時，大頂堆大小應比小頂堆大1
• 當大頂堆的大小超過小頂堆大小1以上時（即maxHeap.size() >= minHeap.size() + 2），需要調整
• 例如：大頂堆有5個元素，小頂堆有3個元素，差值為2，需要調整

為什么小頂堆的條件是 minHeap.size() > maxHeap.size()？

• 當總數字個數為偶數時，兩個堆大小應相等
• 當小頂堆的大小超過大頂堆時（即minHeap.size() >= maxHeap.size() + 1），需要調整
• 例如：小頂堆有4個元素，大頂堆有3個元素，差值為1，需要調整

關鍵差異的原因

大頂堆允許的最大差值是1，小頂堆不允許任何差值

• 大頂堆可以比小頂堆多1個元素（當總元素個數為奇數時）
• 小頂堆不能比大頂堆多元素，最多只能相等（當總元素個數為偶數時）

示例說明

假設當前大頂堆和小頂堆的大小分別為：

• 情況1：maxHeap.size() = 5, minHeap.size() = 3

  • 差值為2，滿足maxHeap.size() > minHeap.size() + 1（5 > 3+1），需要調整
  • 調整后：maxHeap.size() = 4, minHeap.size() = 4

• 情況2：maxHeap.size() = 3, minHeap.size() = 4

  • 滿足minHeap.size() > maxHeap.size()（4 > 3），需要調整
  • 調整后：maxHeap.size() = 4, minHeap.size() = 3

• 情況3：maxHeap.size() = 4, minHeap.size() = 3

  • 差值為1，滿足奇數個元素的條件，無需調整
  • 中位數為大頂堆頂元素

• 情況4：maxHeap.size() = 3, minHeap.size() = 3

  • 滿足偶數個元素的條件，無需調整
  • 中位數為兩個堆頂元素的平均值

總結

堆平衡條件的設計基于以下原則：

1. 大頂堆可以比小頂堆多1個元素（奇數個元素時）
2. 小頂堆不能比大頂堆多元素，最多相等（偶數個元素時）
3. 當大頂堆大小超過小頂堆大小1以上時需要調整（+1的由來）
4. 當小頂堆大小超過大頂堆時需要調整（不需要+1，因為不允許小頂堆更大）

這種條件設計確保了：

• 大頂堆始終保存較小的一半數字
• 小頂堆始終保存較大的一半數字
• 可以在O(1)時間內獲取中位數

理解這些條件背后的原理，有助于更好地掌握雙堆數據結構在中位數查找中的應用。

你修改后的代碼在每次插入新元素時立即排序，雖然簡化了中位數查找的邏輯，但整體效率仍然不如雙堆實現。這是因為排序操作的時間復雜度遠高于堆操作。以下是詳細分析：

一、時間復雜度對比

1. 你的修改版本

• 插入操作 addNum：
  每次插入后排序整個數組，時間復雜度為 O(n log n)，其中 n 是當前元素數量。
  （注：即使使用二分查找找到插入位置，移動元素的時間復雜度仍為 O(n)，整體仍為 O(n)。）

• 查詢操作 findMedian：
  直接訪問中間元素，時間復雜度為 O(1)。

2. 雙堆實現

• 插入操作 addNum：
  維護兩個堆的平衡，時間復雜度為 O(log n)。
  （堆的插入/刪除操作時間為 O(log n)，調整平衡最多兩次堆操作。）

• 查詢操作 findMedian：
  直接訪問堆頂元素，時間復雜度為 O(1)。

3. 性能差異

假設進行 m 次插入和查詢，總時間復雜度：

• 你的實現：O(m × n log n)
  每次插入都需排序整個數組，n 隨插入次數增長，最終接近 m。
• 雙堆實現：O(m × log n)
  每次插入僅需對數時間維護堆平衡。

二、為什么排序效率低？

排序操作（如快速排序、歸并排序）的時間復雜度為 O(n log n)，這在數據量大時非常昂貴。即使你每次插入后立即排序，避免了重復排序的開銷，但單次排序的代價仍然遠高于堆的對數時間操作。

三、示例對比

假設已有 10,000 個元素，插入第 10,001 個元素：

• 你的實現：
  對 10,001 個元素排序，需執行約 10,001 × log?(10,001) ≈ 130,000 次操作。
• 雙堆實現：
  調整兩個堆的平衡，最多需執行 2 × log?(10,001) ≈ 26 次操作。

隨著數據量增長，排序的開銷呈指數級上升，而堆操作始終保持對數時間。

四、優化方向：插入排序（仍不如雙堆）

如果你希望保持數組有序，可以使用插入排序（二分查找定位插入位置），將插入時間優化到 O(n)：

class MedianFinder {
private:vector<int> nums;public:void addNum(int num) {// 二分查找插入位置auto it = lower_bound(nums.begin(), nums.end(), num);nums.insert(it, num);  // 插入操作 O(n)}double findMedian() {int n = nums.size();return n % 2 ? nums[n/2] : (nums[n/2] + nums[n/2-1]) / 2.0;}
};

但插入操作的 O(n) 仍劣于雙堆的 O(log n)，尤其是在數據量大時。

五、雙堆實現的核心優勢

1. 動態維護有序性：
   堆結構通過 O(log n) 時間調整，始終保持堆頂元素為中位數的候選者。

2. 避免全局排序：
   不需要對所有元素排序，僅維護兩個堆的局部有序性，節省大量計算資源。

3. 適用于流數據：
   每次插入和查詢的時間復雜度穩定，即使處理海量數據流也能保持高效。

總結

你的修改版本雖然簡化了代碼邏輯，但每次插入后的排序操作成為性能瓶頸。雙堆實現通過局部有序性和對數時間操作，在動態數據場景下顯著優于全局排序方案。這體現了算法設計中數據結構選擇的重要性——合適的數據結構（如堆）能將問題的時間復雜度從 O(n log n) 優化到 O(log n)。