方法一：插入排序
解题思路
每次添加一个数字时，通过插入排序添加，需要返回中位数时，根据元素个数进行返回。
代码
class MedianFinder {
private:
vector<int> nums;
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
nums.push_back(num);
for (int i = nums.size() - 1; i > 0; i -- ) {
if (nums[i] < nums[i - 1]) swap(nums[i], nums[i - 1]);
else break;
}
}
double findMedian() {
int cnt = nums.size();
if (cnt == 0) return NULL;
int mid = cnt / 2;
if (cnt % 2 == 0) return (nums[mid] + nums[mid - 1]) / 2.0;
else return nums[mid];
}
};
复杂度分析
执行用时：1360 ms, 在所有 C++ 提交中击败了5.04%的用户
内存消耗：40.7 MB, 在所有 C++ 提交中击败了59.16%的用户
通过测试用例：18 / 18
\(addNum()\)：时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)；
\(findMedian()\)：时间复杂度为\(O(1)\)，空间复杂度为\(O(1)\)。
方法二：优先队列
解题思路
通过优先队列维护两个数组\(queMin\) 和 \(queMax\)，\(queMin\)保存数据流中较小的一部分数（从大到小），\(queMax\)保存数据流中较大的一部分数（从小到大），\(queMax.size() - queMin.size() == 0 || 1\)，则样\(queMin.top()\) 和 \(queMax.top()\)就是数据流中间的\(1\)个数 或 中间的\(2\)个数。
代码
class MedianFinder {
private:
priority_queue<int, vector<int>, less<int>> queMin;
priority_queue<int, vector<int>, greater<int>> queMax;
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if (queMin.empty() || num < queMin.top()) {
queMin.push(num);
if (queMax.size() + 1 < queMin.size()) { // queMax元素数量少于queMin元素数量超过1个
queMax.push(queMin.top()); // 将queMin的最大值转移到queMax中，保持平衡
queMin.pop();
}
} else {
queMax.push(num);
if (queMax.size() > queMin.size()) { // queMax元素数量超过queMin元素数量
queMin.push(queMax.top()); // 将queMax的最小值转移到queMin中，保持平衡
queMax.pop();
}
}
}
double findMedian() {
if (queMin.size() > queMax.size()) return queMin.top();
return (queMin.top() + queMax.top()) / 2.0;
}
};
复杂度分析
执行用时：84 ms, 在所有 C++ 提交中击败了93.98%的用户
内存消耗：40.7 MB, 在所有 C++ 提交中击败了33.52%的用户
通过测试用例：18 / 18
\(addNum()\)：时间复杂度为\(O(logn)\)，空间复杂度为\(O(1)\)；
\(findMedian()\)：时间复杂度为\(O(1)\)，空间复杂度为\(O(1)\)。