4 Median of two Sorted Arrays

Method 1: Merge two sorted arrays into one, then use index to find the median element. O(m+n )

Method 2: Binary search. Delete half of the data once. O(log(m+n))

使用 Binary Search的时候，可以考虑以找到左边数组中需要元素的个数作为二分搜索的条件。代码来源于花花酱的博客，花花的视频讲题真的超级优秀！！所有资源在Youtube上面公开，算是很良心啦。

Python

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        merge_arr = []
        p1, p2 = 0, 0
        len1, len2 = len(nums1), len(nums2)
        while True:
            if p1 < len1 and p2 < len2:
                if nums1[p1] <= nums2[p2]:
                    merge_arr.append(nums1[p1])
                    p1 += 1
                else:
                    merge_arr.append(nums2[p2])
                    p2 += 1
            else:
                if p1 == len1:
                    merge_arr.extend(nums2[p2:])
                elif p2 == len2:
                    merge_arr.extend(nums1[p1:])
                break
        if (len1+len2)%2 == 0:
            return (merge_arr[(len1+len2)/2-1] + merge_arr[(len1+len2)/2])/2.0
        else:
            return merge_arr[(len1+len2)/2

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        n = len(nums1)+len(nums2)
        if n%2 == 1:
            return self.findKth(nums1,nums2,n/2+1)
        else:
            smaller = self.findKth(nums1,nums2,n/2)
            bigger = self.findKth(nums1,nums2,n/2+1)
            return (smaller + bigger)/2.0

    def findKth(self, A, B, k):
        # print A, B, k
        if len(A) == 0:
            return B[k-1]
        if len(B) == 0:
            return A[k-1]
        if k == 1:
            return min(A[0],B[0])
        a = A[k/2-1] if len(A) >= k/2 else None
        b = B[k/2-1] if len(B) >= k/2 else None
        if a is None:
            return self.findKth(A,B[k/2:],k-k/2)
        if b is None:
            return self.findKth(A[k/2:],B,k-k/2)
        if(a>b):
            return self.findKth(A,B[k/2:],k-k/2)
        else:
            return self.findKth(A[k/2:],B,k-k/2)

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if(n1 > n2)
            return findMedianSortedArrays(nums2, nums1);
        int k = (n1 + n2 + 1)/2;
        int l = 0;
        int r = n1;
        while(l < r){
            int m1 = l + (r - l)/2;
            int m2 = k - m1;
            if(nums1[m1] < nums2[m2 - 1])
                l = m1 + 1;
            else
                r = m1;
        }
        int m1 = l;
        int m2 = k - l;

        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],
                          m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);
        if((n1 + n2) % 2 == 1)
            return c1;
        else
        {
            int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],
                              m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
            return 0.5*(c1 + c2);
        }
    }
}

Java 小技巧

• 两数中最大最小值： 使用Math包中的max函数和min函数
• 整数中最大最小值：使用Integer包中的MAX_VALUE和MIN_VALUE，类中的静态成员（类成员不会变动）