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))
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.
I don't know either :) There should be others who already posted their O(n) solution.
Shocked...but obviously this code is O(nlogn), as @dewei said, why it can pass all of the test cases?
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
Here's O(log(min(m, n))):
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.