4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution

(1) Java

注意（1）kth的意思是第k个，从1开始，不是从0开始；（2）每次除掉k/2 个或者如果有某个数组长度不到k/2，就比较它的最大元素和另一个数组的k/2-1元素的大小，把小的那部分去掉

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length+nums2.length;
        return len%2==0 ? 
                (findKthNum(nums1, nums2, len/2, 0, 0)+findKthNum(nums1, nums2, len/2+1, 0, 0))/2.0 :
                findKthNum(nums1, nums2, len/2+1, 0, 0)/1.0;
    }

    private int findKthNum(int[] nums1, int[] nums2, int kth, int start1, int start2) {
        if (start1 >= nums1.length) {
            return nums2[start2+kth-1];
        }
        if (start2 >= nums2.length) {
            return nums1[start1+kth-1];
        }
        if (kth == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        }
        int len1 = nums1.length-start1;
        int len2 = nums2.length-start2;
        int key1 = Math.min(len1, kth/2);
        int key2 = Math.min(len2, kth/2);
        if (nums1[start1+key1-1] < nums2[start2+key2-1]) {
            return findKthNum(nums1, nums2, kth-key1, start1+key1, start2);
        } else {
            return findKthNum(nums1, nums2, kth-key2, start1, start2+key2);
        }
    }
}

(2) Python

I tried to cut half from list instead of k, but there are too many corner cases, so still stick to k/2, much more simpler code:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def findKth(nums1, nums2, k):
            if not nums1:
                return nums2[k-1]
            if not nums2:
                return nums1[k-1]
            if k == 1:
                return min(nums1[0], nums2[0])
            mid1, mid2 = min(len(nums1), k/2), min(len(nums2), k/2)
            return findKth(nums1[mid1:], nums2, k-mid1) if nums1[mid1-1] <= nums2[mid2-1] else findKth(nums1, nums2[mid2:], k-mid2)

        return (findKth(nums1, nums2, (len(nums1)+len(nums2)+1)/2)+findKth(nums1, nums2, (len(nums1)+len(nums2)+2)/2))/2.0

(3) Scala

object Solution {
    def findMedianSortedArrays(nums1: Array[Int], nums2: Array[Int]): Double = {
        val mid1 = (nums1.length+nums2.length+1)/2
        val mid2 = (nums1.length+nums2.length+2)/2
        val rst = (findKth(nums1, 0, nums2, 0, mid1)+findKth(nums1, 0, nums2, 0, mid2))/2.0
        return rst
    }

    def findKth(nums1: Array[Int], start1: Int, nums2: Array[Int], start2: Int, k: Int): Int = {
        if (start1 >= nums1.length) {
            return nums2{start2+k-1}
        }
        if (start2 >= nums2.length) {
            return nums1{start1+k-1}
        }
        if (k==1) {
            return Math.min(nums1{start1}, nums2{start2})
        }
        val half1 = Math.min(nums1.length-start1, k/2)
        val half2 = Math.min(nums2.length-start2, k/2)
        if (nums1{start1+half1-1} < nums2{start2+half2-1}) {
            return findKth(nums1, start1+half1, nums2, start2, k-half1)
        } else {
            return findKth(nums1, start1, nums2, start2+half2, k-half2)
        }
    }
}