Median of Two sorted Arrays

这是一道属于quick select的变种类型题，和quick select不同的是数组已经排好序且数组有两个，我们要找的是两个数组合并之后的中位数，这里最关键的一点就是要发现找第k个数的时候，有一个关键的前提即如果A[k / 2 - 1] < B[k / 2 - 1]则表示，A的前k/2数必然是在前k个里面的，我们可以直接把这个k/2个数砍掉，反之亦然，有了这个前提就相当于我们可以把O(k)的问题转化为一个O(k/2)的问题且只用O(1)的时间，泛化到整个数组也就是O(lgn)的总时间复杂度了，下面是代码

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

    def findKth(self, A, startA, B, startB, k):
        if startA >= len(A):
            return B[startB + k - 1]
        if startB >= len(B):
            return A[startA + k - 1]
        if k == 1:
            return min(A[startA], B[startB])
        A_key = A[startA + k / 2 - 1] if startA + k / 2 - 1 < len(A) else sys.maxint
        B_key = B[startB + k / 2 - 1] if startB + k / 2 - 1 < len(B) else sys.maxint 

        if A_key < B_key:
            return self.findKth(A, startA + k / 2, B, startB, k - k / 2)
        return self.findKth(A, startA, B, startB + k / 2, k - k / 2)

Java版本

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        if ((n + m) % 2 == 1) {
            return findKth(nums1, 0, nums2, 0, (n + m) / 2 + 1);
        }
        return (findKth(nums1, 0, nums2, 0, (n + m) / 2 + 1) + 
                findKth(nums1, 0, nums2, 0, (n + m) / 2)) / 2.0;
    }

    private int findKth(int[] numsA, int startA, int[] numsB, int startB, int k) {
        if (startA >= numsA.length) {
            return numsB[startB + k - 1];
        }
        if (startB >= numsB.length) {
            return numsA[startA + k - 1];
        }
        if (k == 1) {
            return Math.min(numsA[startA], numsB[startB]);
        }
        int baseA = Integer.MAX_VALUE;
        int baseB = Integer.MAX_VALUE;
        if (startA + k / 2 - 1 < numsA.length) {
            baseA = numsA[startA + k / 2 - 1];
        }
        if (startB + k / 2 - 1 < numsB.length) {
            baseB = numsB[startB + k / 2 - 1];
        }

        if (baseA < baseB) {
            return findKth(numsA, startA + k / 2, numsB, startB, k - (k / 2));
        }
        return findKth(numsA, startA, numsB, startB + k / 2, k - (k / 2));
    }
}