Leetcode 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

This problem requires a relatively high efficiency.

The problem requires the median of two sorted arrays. We know that for one sorted array, the median is the length/2 number when length of the array is even, length/2 + 1 when odd. So actually we can convert this problem to an even more common problem: how to find Kth number from two sorted array?

The straight forward thought is to merge and then get the Kth number, while the time complexity is not acceptable. Actually we should take the advantage of two sorted arrays.

The solution is to remove K/2 elements from two arrays recursively. There are two problems: what if the length is not enough and which part to get rid of?

The first problem is simple: because we do it recursively, we can always put this under control.

The second problem requires some thought. There are only two case: the wanted number is in the range or not. Unfortunately we cannot decide it is in or not, but something is true: we can always remove some part. Because we pick K elements from two arrays, if the wanted number is in the K elements, it should be the largest number; else, it should be even larger. In both cases, the smaller part can be removed because the wanted number is not there for sure.

Also there are other ways to achieve this purpose. [Reference: kamyu104's GitHub]

Solution with 3 different functions to find Kth number:

# T:O(lg(m+n)) S:O(1)
class Solution:
    # @param {integer[]} nums1
    # @param {integer[]} nums2
    # @return {float}
    def findMedianSortedArrays(self, A, B):
        lenA, lenB = len(A), len(B)
        if (lenA + lenB) % 2 == 1: 
            return self.getKth(A, B, (lenA + lenB)/2 + 1)
        else:
            return (self.getKth(A, B, (lenA + lenB)/2) + self.getKth(A, B, (lenA + lenB)/2 + 1)) * 0.5

    def getKth(self, A, B, k):
        if len(A) < len(B):
            temp = B
            B = A
            A = temp   # make sure A is longer or equal
        if not B:   # if B is empty
            return A[k - 1]
        if k == 1:   # if just need the min
            return min(A[0], B[0])
        if k == (len(A)+len(B)):   # if just need the max
            return max(A[len(A)-1], B[len(B)-1])
        pb = min(k/2, len(B))   # normally we want k/2 for each list, while B might be out of length
        pa = k - pb
        if A[pa - 1] > B[pb - 1]:
            return self.getKth(A, B[pb:], k - pb)   # delete from B
        elif A[pa - 1] < B[pb - 1]:
            return self.getKth(A[pa:], B, k - pa)   # delete from A
        else:
            return A[pa - 1]   # if =, the kth number is just here

'''Other two functions to achieve finding Kth number:
    def getKth(self, A, B, k):
        m, n = len(A), len(B)
        if m > n:
            return self.getKth(B, A, k)
            
        left, right = 0, m    
        while left < right:
            mid = left + (right - left) / 2
            j = k - 1 - mid
            if 0 <= j and j < n and A[mid] >= B[j]:
                right = mid
            else:
                left = mid + 1
            
        Ai_minus_1, Bj = float("-inf"), float("-inf")
        if left - 1 >= 0:
            Ai_minus_1 = A[left - 1]
        if k - 1 - left >= 0:
            Bj = B[k - 1 - left]
        
        return max(Ai_minus_1, Bj)

    def getKth(self, A, B, k):
        b = max(0, k - len(B))
        t = min(len(A), k)
        while b < t:
            x = b + (t - b) / 2
            A_x_1, A_x, B_k_x_1, B_k_x = float("-inf"), float("inf"), float("-inf"), float("inf")
            if x > 0:
                A_x_1 = A[x - 1]
            if x < len(A):
                A_x = A[x]
            if k - x > 0:
                B_k_x_1 = B[k - x - 1]
            if k - x < len(B):
                B_k_x = B[k - x]
            
            if A_x < B_k_x_1:
                b = x + 1
            elif A_x_1 > B_k_x:
                t = x - 1
            else:
                return max(A_x_1, B_k_x_1)
        
        A_b_1, B_k_b_1 = float("-inf"), float("-inf")
        if b > 0:
            A_b_1 = A[b - 1]
        if k - b - 1 >= 0:
            B_k_b_1 = B[k - b - 1]
            
        return max(A_b_1, B_k_b_1)''' 

Run Time: 112 ms