Is there anything wrong in my code?


  • 0

    My code got accepted. So simple code. But when I look into others code in discussion I saw that they use iterative solution or used Binary search and also the category for this problem is given hard. So I am curious if my solution accidentally pass all the test cases :p Please let me know. Here is my code.
    ...
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        nums1.insert(nums1.end(), nums2.begin(), nums2.end());
        
        sort(nums1.begin(), nums1.end());
        
        int sz = nums1.size();
        
        if(sz % 2 == 1)
        {
            return (double) nums1[sz/2];
        }
        else
        {
            return (double) (nums1[(sz/2)-1] + nums1[sz/2]) / 2.0;
        }
        
        
    }
    

    ...


  • 0
    T

    It's O((n+m)log(n+m)) algorithm, the question requires O(log(n+m)), so your algorithm is slow, it is so weird that it should receive TLE


  • 0

    Is my program slow because of the sort function? I'm a beginner so please help.


  • 2
    C

    sort function use O(nlogn), so, it is that sort function make your program slow


  • 1
    E

    @shadab_the_cryptocoder yes, sorting makes it slow.

    Take a look here and see if this helps: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

    The very short version is, some operations can take a huge amount of time to run depending on the size of the data set you're working with. When sorting a collection, every extra element increases the time it takes to sort the whole thing.

    Your original solution is what's typically referred to as a 'naive' solution. It's logically correct, but it's significantly less efficient than it could be, because you're not making use of some guarantees you have about the problem space.

    In this case, you start with 2 sorted lists, but you're discarding that information, slapping them in one shared list, and sorting the whole thing. You can solve it much more efficiently if you use the fact that the two are already sorted (even though they aren't sorted together).


  • 0
    S

    @enroth Thanks a ton! :)


Log in to reply
 

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