Python solution

  • 0

    I don't know if it's kosher, but I saw no reason not to use the built-in sort method for lists!

    m = len(nums1)
    n = len(nums2)
    combo = nums1 + nums2
    x = m + n
    if (x % 2): # odd number of merged array elements -- median equals middle element
        mid = (x - 1) / 2
        median = combo[mid]
    else: # even number of merged array elements -- median equals average of middle two elements
        mid = x / 2
        median = (combo[mid-1] + combo[mid]) / float(2)

  • 0

    @riemannzeta interested in this, because I was tempted to write it and submit it.
    Have you submitted it? Does it pass all tests?

    Thing is, from other bechmarks (see also this one ), the simple python solution using the built-in addition operator (or .extend) on lists, and then the sort/sorted() method is faster than a custom-made merge-sort algorithm. This seems true all the way to about 1,000,000 (1M) items among the starting lists.

    Of course, the problem statement includes the note that The overall run time complexity should be O(log (m+n)).
    The python built-in sort() and sorted() methods seem to rely on Timsort, so they run in O(n log(n) ) (of course, the 'n' in this case is the 'm+n' of the problem statement).
    But I wonder if LeetCode has test cases for this problem that detect the difference between O(n log(n) ) and the requested O(log(n) ) solution.

  • 1

    I have submitted it and it passed all test, placing it high among accepted answers.

    I didn't bother to check whether the built-in sort function would be O(log(n)) vs. O(n log(n)). Thanks for sharing that. I just know that built-ins will outperform what I code up most of the time, and nearly all of the time if you factor in the extra time required to write the custom sorting algorithm.

    I know that's not the point of these exercises, but I think it highlights the downside to spending too much time on these kinds of problems. Yes, it's good to know the difference between O(n log(n)) and O(log(n)), but how often does it really matter in practice for most engineers?

  • 0

    @riemannzeta said in Python solution:

    I didn't bother to check whether the built-in sort function would be O(log(n)) vs. O(n log(n)).

    Um... how could it possibly be O(log(n))? That doesn't even allow looking at all elements.

    Only seems fast because the judge is very weak here, perhaps because this is from the earliest days of LeetCode. Of the 2080 test cases, only 21 have more than 10 elements (in nums1 and nums2 combined). And the largest has only 1000+1000=2000 elements and the total number of elements in all 2080 test cases is only 49541. But that's all rather irrelevant, as the problem clearly requests O(log (m+n)) so it's clear you haven't actually solved the problem.

Log in to reply

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