C++ | Leetcode C++题解之第295题数据流的中位数
题目:
题解:
class MedianFinder {multiset<int> nums;multiset<int>::iterator left, right;public:MedianFinder() : left(nums.end()), right(nums.end()) {}void addNum(int num) {const size_t n = nums.size();nums.insert(num);if (!n) {left = right = nums.begin();} else if (n & 1) {if (num < *left) {left--;} else {right++;}} else {if (num > *left && num < *right) {left++;right--;} else if (num >= *right) {left++;} else {right--;left = right;}}}double findMedian() {return (*left + *right) / 2.0;}
};