A Python solution - O(n/2) 171ms


  • 0
    G

    I know, I know, this is not the O(logn) solution :) But this is definitely the most intuitive one

    class Solution:
        # @return a float
        def findMedianSortedArrays(self, A, B):
            med1 = med2 = i = j = 0
            n = len(A) + len(B)
            
            while (i + j) <= n / 2:
                if i < len(A) and j < len(B):
                    med2 = med1
                    if A[i] < B[j]:
                        med1 = A[i]
                        i += 1
                    else:
                        med1 = B[j]
                        j += 1
                elif i < len(A):
                    med2 = med1
                    med1 = A[i]
                    i += 1
                elif j < len(B):
                    med2 = med1
                    med1 = B[j]
                    j += 1
    
            if n % 2 == 0:
                return (med1 + med2) / 2.0
            else:
                return med1

Log in to reply
 

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