Find median in two sorted array - not optimal but acceptable solution

• Hi, this solution has been totally accepted by online judge, but I think that we have memory overhead. It should be something like iteration over nums1 and nums2 approach to identify the median...

class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

``````    std::vector<int> nums12;

nums12.reserve(nums1.size() + nums2.size());
nums12.insert(nums12.end(), nums1.begin(), nums1.end());
nums12.insert(nums12.end(), nums2.begin(), nums2.end());

std::sort(nums12.begin(), nums12.end());

if(nums12.size()%2)
return nums12[nums12.size()/2];
else
return (double)(nums12[nums12.size()/2 - 1] + nums12[nums12.size()/2])/2;
}
``````

};

• I don't find this acceptable. The problem says "The overall run time complexity should be O(log (m+n))", which your code clearly violates.

• The best sort algorithm has the complexity of nlog(n). Thus, your solution time complexity is (m+n)log(m+n) at best.

• So, does it mean merging two arrays together is not allowed?

• What are you wondering about? The complexity or the "should be"?

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