图片.png

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<stack>
#include<string>
#include <set>
#include <unordered_set>
#include <map>
//* Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//Definition for singly-linked list.
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };
//ans
class MedianFinder {
public:
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (small.size() < large.size()) {
            small.push(-large.top());
            large.pop();
        }
    }

    // Returns the median of current data stream
    double findMedian() {
        return small.size() > large.size() ? small.top() : 0.5 *(small.top() - large.top());
    }

private:
    priority_queue<long> small, large;
};

//i81
class Solution {
private:
    priority_queue<int> small, large;
public:
    void addNum(int num) {
        small.push(num);
        large.push(-small.top());
        small.pop();
        if (large.size() > small.size()) {
            small.push(-large.top());
            large.pop();
        }

    }
    double findMedian() {
        return small.top();
    }
    vector<int> medianII(vector<int> &nums) {
        vector<int> ans;
        for (auto aa : nums) {
            addNum(aa);
            ans.push_back(findMedian());
        }
        return ans;
    }
};

int main()
{
    vector<int> aa = { 1,2,22,1,3,1,1,7,8,5 };
    MedianFinder ss;
    double ans;
    ss.addNum(3);
    ans = ss.findMedian();
    ss.addNum(4);
    ans = ss.findMedian();
    ss.addNum(2);
    ans = ss.findMedian();
    ss.addNum(10);
    ans = ss.findMedian();
    ss.addNum(100);
    ans = ss.findMedian();
    //vector<vector<int>> ans(23, vector<int>());

    getchar();
    return 0;
}

图片.png