Use binary search O(lgn) to insert, and O(1) to retrieve the median.


  • 1
    J
    class MedianFinder {
    private:
        vector<int> nums;
    public:
        /** initialize your data structure here. */
        MedianFinder() {
            nums = vector<int>();
        }
        
        void addNum(int num) {
            int l=0;
            int r=nums.size()-1;
            while (l<=r){
                int mid = l + (r-l)/2;
                if (nums[mid]==num){
                    nums.insert(nums.begin()+mid, num);
                    return;
                }
                else if (num<nums[mid]) r = mid-1;
                else l = mid+1;
            }
            nums.insert(nums.begin()+l, num);
            return;
        }
        
        double findMedian() {
            return nums.size()%2 ? nums[(nums.size()-1)/2]: (nums[(nums.size()-1)/2]+nums[(nums.size()-1)/2+1])/2.0;
        }
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */
    

Log in to reply
 

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