Share my Python code


  • 0
    W
    class Solution:
        # @return a float
        def findMedianSortedArrays(self, A, B):
            n=len(A)
            m=len(B)
            if n>m:
                return self.findMedianSortedArrays(B,A)
            if n==0 and m%2==1:
                return B[m/2]
            elif n==0 and m%2==0:
                return 0.5*(B[m/2-1]+B[m/2])
            elif n==1 and m%2==0:
                if A[0]<=B[m/2-1]:
                    return B[m/2-1]
                elif A[0]>=B[m/2]:
                    return B[m/2]
                else:
                    return A[0]
            elif n==1 and m==1:
                return 0.5*(A[0]+B[0])
            elif n==1 and m%2==1:
                if A[0]<=B[(m-1)/2]:
                    return 0.5*(max(B[(m-3)/2],A[0])+B[(m-1)/2])
                else:
                    return 0.5*(min(B[(m+1)/2],A[0])+B[(m-1)/2])
            elif n==2 and m%2==1:
                if A[1]<=B[(m-1)/2]:
                    return max(A[1],B[(m-3)/2])
                elif A[0]>=B[(m-1)/2]:
                    return min(A[0],B[(m+1)/2])
                else:
                    return B[(m-1)/2]
            elif n==2 and m==2:
                return 0.5*(max(A[0],B[0])+min(A[1],B[1]))
            elif n==2 and m%2==0:
                if A[1]<=B[m/2]:
                    return 0.5*(max(A[0],B[m/2-1])+max(A[1],B[m/2-2]))
                elif A[0]>=B[m/2-1]:
                    return 0.5*(min(A[0],B[m/2+1])+min(A[1],B[m/2]))
                else:
                    return 0.5*(B[m/2-1]+B[m/2])
            elif n==3 and m==3:
                if A[1]>=B[1]:
                    return 0.5*(max(A[0],B[1])+min(A[1],B[2]))
                else:
                    return 0.5*(max(A[1],B[0])+min(A[2],B[1]))
            elif n==3 and m%2==1:
                if A[1]>=B[(m-1)/2]:
                    return self.findMedianSortedArrays(A[:2],B[1:])
                else:
                    return self.findMedianSortedArrays(A[1:],B[:(m-1)])
            elif n==3 and m%2==0:
                if A[1]>=B[m/2]:
                    return self.findMedianSortedArrays(A[:2],B[1:])
                else:
                    return self.findMedianSortedArrays(A[1:],B[:(m-1)])
            elif n==4 and m==4:
                if A[1]>=B[2]:
                    return 0.5*(max(A[0],B[2])+min(A[1],B[3]))
                else:
                    return self.findMedianSortedArrays(A[1:],B[:3])
            elif n%2==1 and m%2==0:
                if A[(n-1)/2]>=B[m/2-1]:
                    return self.findMedianSortedArrays(A[:(n+1)/2],B[(n-1)/2:])
                else:
                    return self.findMedianSortedArrays(A[(n-1)/2:],B[:(2*m-n+1)/2])
            elif n%2==1 and m%2==1:
                if A[(n-1)/2]>=B[(m-1)/2]:
                    return self.findMedianSortedArrays(A[:(n+1)/2],B[(n-1)/2:])
                else:
                    return self.findMedianSortedArrays(A[(n-1)/2:],B[:(2*m-n+1)/2])
            elif n%2==0 and m%2==1:
                if A[n/2-1]>=B[(m-1)/2]:
                    return  self.findMedianSortedArrays(A[:n/2],B[n/2:])
                else:
                    return self.findMedianSortedArrays(A[n/2-1:],B[:(2*m-n+2)/2])
            elif n%2==0 and m%2==0:
                if A[n/2-1]<=B[m/2]:
                    return self.findMedianSortedArrays(A[n/2-1:],B[:(2*m-n+2)/2])
                else:
                    return self.findMedianSortedArrays(A[:n/2+1],B[n/2-1:])

Log in to reply
 

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