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

• ``````class MedianFinder {
public:
vector<int> nums;
double n1,n2;
// Adds a number into the data structure.
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 ?

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

• @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}

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

• 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()`).

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

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

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

• @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.
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;
}
};
``````

• @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.
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;
}
};
``````

• @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.
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;
}
};
``````

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