Sharing my 108ms Python Solution


  • -7
    A
    class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            def median(a):
                if len(a) % 2 != 0:
                    return a[len(a)//2]
                else:
                    return ((a[len(a)/2]+a[(len(a)/2)-1])/2.)
            temp = nums1+nums2
            temp.sort()
            return (median(temp))

  • 0
    D

    I also used this way, but the complexity of sort() is O(nlog(n))
    There is space to improve.
    I guess bi-search is the direction.


  • 0
    A

    How can I improve on the sort step?


  • 0
    D

    I don't know either :) There should be others who already posted their O(n) solution.


  • 0
    W

    Shocked...but obviously this code is O(nlogn), as @dewei said, why it can pass all of the test cases?


  • 0
    A

    Well, by the definition of a median of a sorted array, even numbered arrays wok have a median of the middle 2 elements, and odd numbered arrays will have a median of the middle element. So by manipulating the indicies of a sorted array, we can ignore all other elements and reach the median quickly. My only downfal is the sort function, which I Appreciate Any help with


  • 0
    Z

Log in to reply
 

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