Niuke.com: median in data flow

 

There are three ways to solve this problem

Catalog

1. violence

2. Insertion sort

3. Pile up

---

1. violence

Read all the data directly and then use sort Sort the output median .

Here the type conversion uses C++11 Of static_cast<>

Because it is a fast platoon , So the time complexity is O(nlogn)

The code is as follows ：

class Solution {
public:
    #define SCD static_cast<double>
    vector<int> v;
    void Insert(int num) {
        v.push_back(num);
    }

    double GetMedian() { 
        sort(v.begin(), v.end());
        int sz=v.size();
        if(sz & 1){// Odd numbers return the middle digit 
            return SCD(v[sz>>1]);
        }else{
            return SCD(v[sz>>1]+v[(sz>>1)-1])/2;
        }
    }

};

2. Insertion sort

Here's one lower_bound Interface ：

Its function is to return the first value in the array that is greater than or equal to the checked number

The method of finding the median is no different from that before .

The time complexity here is for each number O(logn) Of , The total time complexity is zero O(nlogn)

class Solution {
public:
    #define SCD static_cast<double>
    vector<int> v;
    void Insert(int num) {
        if(v.empty()){
            v.push_back(num);
        }else{
            auto it=lower_bound(v.begin(), v.end(), num);
            v.insert(it, num);
        }
    }

    double GetMedian() { 
        int sz=v.size();
        if(sz&1){
            return SCD(v[sz>>1]);
        }else{
            return SCD(v[sz>>1]+v[(sz>>1)-1])/2;
        }
    }

};

3. Pile up

Here's how to write the big and small top heap directly ：

Small cap pile ：

priority(int, vector<int>, less<int>)

Big pile top ：

priority(int, vector<int>, greater<int>)

Our task is to maintain two top size heaps , It's understandable , We only need to use two numbers to separate the small and large parts , Why must two parts be ordered ？ Based on this consideration , We use heap sort .

Pay attention to some details , The small part is stored in the big top pile , The large part is stored in the small top pile .

Ideas as follows ：

Since it is the median requirement , We want the number of elements in the two heaps to be as close as possible , It can be divided into the following situations ：

1. The number of elements in the large top heap is more than that in the small top heap , If we want to put new data in at this time , Obviously we should put it on the small top pile , But is it the new element we are adding now ？ Obviously not , We should make use of the big top pile at this time , First, put the current element into the big top heap , Then take out the newly generated heap top and put it into the small top heap .

2. The rest is pretty much the same , It means that you put it in any heap .

At this time, the median is calculated according to the number of elements in the two heaps

The code is as follows ：

class Solution {
public:
    #define SCD static_cast<double>
    priority_queue<int> min_q;// Small cap pile 
    priority_queue<int, vector<int>, greater<int>> max_q;// Big pile top 
    void Insert(int num) {
        if(max_q.size()>=min_q.size()){
            max_q.push(num);
            min_q.push(max_q.top());
            max_q.pop();
        }else{
            min_q.push(num);
            max_q.push(min_q.top());
            min_q.pop();
        }
    }

    double GetMedian() { 
        if(max_q.size()==min_q.size()){
            return SCD(max_q.top()+min_q.top())/2;
        }else if(max_q.size()>min_q.size()){
            return SCD(max_q.top());
        }else{
            return SCD(min_q.top());
        }
    }

};