Binary Search + vector insert .time complexity O(logn +n). 150ms


  • 0
    S
    class MedianFinder {
    public:
    /*
        
    */
    
        // Adds a number into the data structure.
        vector<int> v;
        void addNum(int num) {
            int low=0,high=(int)(v.size())-1;
            while(low<=high){
                int mid=low+(high-low)/2;
                if(v[mid]<num) low=mid+1;
                else high=mid-1;
            }
            v.insert(v.begin()+low,num);
        }
    
        // Returns the median of current data stream
        double findMedian() {
            double res=0;
            if(v.size()%2==0){
                res=(v[v.size()/2]+v[v.size()/2-1]);
                res/=2.0f;
            }
            else res=v[v.size()/2];
            return res;
        }
    };
    
    // Your MedianFinder object will be instantiated and called as such:
    // MedianFinder mf;
    // mf.addNum(1);
    // mf.findMedian();
    

  • 0
    A

    @shx vector.insert() is not O(logN), it is O(N). So O(logN + N) == O(N).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.