Could this problem be solved using nth_element() in C++?


  • 0
    J
    class MedianFinder {
    public:
       vector<int> nums;
       double n1,n2;
       // Adds a number into the data structure.
       void addNum(int num) {
    	   nums.push_back(num);
    	   
    	   int size = nums.size();
    	   vector<int>::iterator m1 = nums.begin() + (size - 1) / 2;
    	   vector<int>::iterator m2 = nums.begin() + (size - 1) / 2 + 1;
    	   if (size % 2 == 0){
    		   nth_element(nums.begin(), m1, nums.end());
    		   nth_element(nums.begin(), m2, nums.end());
    		   n1 = (double)nums[(size - 1) / 2];
    		   n2 = (double)nums[(size - 1) / 2 + 1];
    	   }else{
    		   nth_element(nums.begin(), m1, nums.end());
    		   n1 = (double)nums[(size - 1) / 2];	
    		   n2 = n1;
    	    }
       }
    
       // Returns the median of current data stream
       double findMedian() {
             return (n1 + n2) / 2.0;
       }
    };
    

    I think my logic is right. However, this code is WA. Could you tell me where the error is ?


  • 0

    vector here cannot ensure its sorted properly using set or multset could be okay here.


  • 0
    J

    @LHearen
    why cant vector here ensure its sorted properly? Actually , I run the code in VS2013 and got the right answer while the nums is {1,2,3,4,5,6,7,8,9,10}


  • 0

    @JerryFeng then how about we adding numbers as 2, 4, 3, 1?


  • 0

    Not sure why you guys are talking about sorted. The code is only using nth_element.

    The problem is that the second nth_element destroys the achievement of the first. So do n1 = (double)nums[(size - 1) / 2]; before nth_element(nums.begin(), m2, nums.end());. Or instead, use nth_element(m2, m2, nums.end()); (or more efficiently, just find the minimum from m2 to nums.end()).


  • 0

    @StefanPochmann Your idea is also about sorted position, isn't it? Of course, using nth_element in C++ is quite cool.


  • 0

    @LHearen It's related to sortedness but sortedness is far stronger and not needed here.


  • 0

    @StefanPochmann Yes, couldn't agree more on this!


  • 0

    @JerryFeng Indeed, your logic is right but its performance is bad since each time it will cost O(n) to retrieve the median.
    B.T.W. Your solution can be corrected as follows but TLE due to its inefficiency.

    class MedianFinder {
    private:
        vector<int> arr;
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            arr.push_back(num);
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if(arr.empty()) return 0;
            double ret;
            auto mid = arr.begin()+arr.size()/2;
            if(arr.size() & 1) 
            {
                nth_element(arr.begin(), mid, arr.end());
                ret = *mid;
            }
            else 
            {
                nth_element(arr.begin(), prev(mid), arr.end());
                nth_element(mid, mid, arr.end());
                ret = (*prev(mid)+*mid)/2.0;
            }
            return ret;
        }
    };
    

  • 0

    @JerryFeng While using multiset not only will satisfy the efficiency but will also allow duplicates, solution in C++ enclosed as follows.

    class MedianFinder {
    private:
        multiset<int> dataStream;
        multiset<int>::iterator m_iter;
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            dataStream.insert(num);
            if(dataStream.size() == 1) { m_iter = dataStream.begin(); return ; }
            if(dataStream.size()%2==0 && num<*m_iter) m_iter = prev(m_iter);
            if(dataStream.size()%2==1 && num>=*m_iter) m_iter = next(m_iter);
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if(dataStream.size() & 1) return *m_iter;
            else return (*m_iter+*next(m_iter))/2.0;
        }
    };
    

  • 0

    @JerryFeng Another solution using max_heap from StefanPochmann for your reference

    class MedianFinder {
    private:
        priority_queue<long> less, greater;
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            less.push(num);
            greater.push(-less.top());
            less.pop();
            if(less.size() < greater.size())
            {
                less.push(-greater.top());
                greater.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            return less.size() > greater.size()? less.top() : (less.top()-greater.top())/2.0;
        }
    };
    

Log in to reply
 

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