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


  • 0
    S

    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...

    Any comments would be appreciated.

    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;
    }
    

    };


  • 1

    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.


  • 0
    V

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


  • 0
    L

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


  • 0

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


Log in to reply
 

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