LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 用大顶堆保存左半边元素，用小顶堆各保存右半边元素，中位数即为二者堆顶值之一或平均数

class MedianFinder {
 public:
  /** initialize your data structure here. */
  MedianFinder() {}

  void addNum(int num) {
    if (q1.empty()) {
      q1.emplace(num);
      return;
    }
    if (num <= q1.top()) {
      q1.emplace(num);
      if (q1.size() == q2.size() + 2) {
        q2.emplace(q1.top());
        q1.pop();
      }
    } else {
      q2.emplace(num);
      if (q1.size() == q2.size() - 2) {
        q1.emplace(q2.top());
        q2.pop();
      }
    }
  }

  double findMedian() {
    if (q1.size() > q2.size()) {
      return q1.top();
    }
    if (q1.size() < q2.size()) {
      return q2.top();
    }
    return (q1.top() + q2.top()) / 2.0;
  }

 private:
  priority_queue<int> q1;  // 大顶堆
  priority_queue<int, vector<int>, greater<int>> q2;
};