LeetCode 295 Find Median from Data Stream
概述
https://leetcode.com/problems/find-median-from-data-stream/
这是一道 Hard 题。
注意是求中值，输入未必是按顺序的。
涉及到求 int 类型的中值，注意类型转换。
基于二分搜索树的解法
不知道为啥让我想起平衡的二分搜索树。
如果二分搜索树的左右子树元素个数相同，那中值就是根节点的值。
实际上确实也不需要平衡的二叉树，只要左右子树元素个数一致或仅差一，那我们只需要根节点和左右子节点以及左右子树元素个数就可以算出中值。
加入新的值时：
- 如果加给了右子树，将右子树的根节点提升为总的根节点，原根节点接到其左子树位置，原左子树接到原根节点右子树位置；
- 如果加给了左子树，将左子树的根节点提升为总的根节点，原根节点接到其右子树位置，原右子树接到原根节点左子树位置。
搞错了一点，我们需要左子树中的最大值，以及右子树中的最小值。
emmm，插入 BST 的代码写错，de 了半天 bug 才发现。。。
以下是一个不能通过所有用例的错误解法，我猜错误原因在于换 root 那里，这个的 BST 里有重复元素，不想再 debug 了，毁灭吧，赶紧的。
class MedianFinder {
public:
class Node {
public:
Node* left = nullptr;
Node* right = nullptr;
int val;
Node(int val) {
this->val = val;
}
};
Node* root = nullptr;
int lc = 0;
int rc = 0;
MedianFinder() {
}
void addNum(int num) {
if (root) {
root = insertIntoBST(root, num);
if (num <= root->val) {
lc ++;
if (lc - rc >= 2) {
lc --;
rc ++;
auto oldRoot = root;
root = oldRoot->left;
oldRoot->left = root->right;
root->right = oldRoot;
}
} else {
rc ++;
if (rc - lc >= 2) {
rc --;
lc ++;
auto oldRoot = root;
root = oldRoot->right;
oldRoot->right = root->left;
root->left = oldRoot;
}
}
} else {
root = new Node(num);
}
}
double findMedian() {
if (lc > rc) return (double(root->val) + leftMax()) / 2;
if (lc < rc) return (double(root->val) + rightMin()) / 2;
return root->val;
}
int leftMax() {
auto node = root->left;
if (node->right) {
node = node->right;
}
return node->val;
}
int rightMin() {
auto node = root->right;
if (node->left) {
node = node->left;
}
return node->val;
}
Node* insertIntoBST(Node* root, int num) {
if (!root) return new Node(num);
if (num < root->val) {
root->left = insertIntoBST(root->left, num);
} else if (num > root->val) {
root->right = insertIntoBST(root->right, num);
} else {
auto newLeft = new Node(num);
newLeft->left = root->left;
root->left = newLeft;
}
return root;
}
};
基于双优先级队列的解法
https://mp.weixin.qq.com/s/oklQN_xjYy--_fbFkd9wMg
简单地说，一个最小堆，一个最大堆，两个堆元素个数相同或只差 1，且最小堆中所有元素比最大堆大。
绝了，要是能想清楚，这种 Hard 题实现起来也并不算麻烦。
class MedianFinder {
public:
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int>> minHeap;
MedianFinder() {
}
void addNum(int num) {
if (maxHeap.size() > minHeap.size()) {
if (num >= maxHeap.top()) {
minHeap.push(num);
} else {
minHeap.push(maxHeap.top());
maxHeap.pop();
maxHeap.push(num);
}
} else {
if (minHeap.empty()) {
minHeap.push(num);
return;
}
if (num <= minHeap.top()) {
maxHeap.push(num);
} else {
maxHeap.push(minHeap.top());
minHeap.pop();
minHeap.push(num);
}
}
}
double findMedian() {
if (maxHeap.size() > minHeap.size()) return maxHeap.top();
if (maxHeap.size() < minHeap.size()) return minHeap.top();
return (double(maxHeap.top()) + double(minHeap.top())) / 2;
}
};