**Median of Two Sorted Arrays

Median of Two Sorted Arrays

对于中位数问题，首先要做的是明白“找中位数” 等价于 find kth largest element，奇数元素找一遍，偶数元素找两遍。

所谓 “第 kth 的元素”，也叫 Order Statistic，在算法导论上有章节对这类问题有很详细的描述。

有向箭头"A -> B"代表 "A > B"，图中黑点为元素(quick-select 分组出来的，不是排序)，白点为分组中位数，阴影部分元素，都一定比 x 大。

这个算法的核心思想是，每次可以扔掉 A 或 B 里面，较小的那 k / 2 个数，使得 A 与 B 的剩余搜索范围单调向右，而 k 指数缩小。

复杂度 O(log k)，k = (m + n) / 2

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

    private int findKth(int[] A, int startA, int[] B, int startB, int k){
        if(startA == A.length) return B[startB + k - 1];
        if(startB == B.length) return A[startA + k - 1];
        if(k == 1) return Math.min(A[startA], B[startB]);

        int keyA = (startA + k / 2 - 1 < A.length)
                    ? A[startA + k / 2 - 1]
                    : Integer.MAX_VALUE;
        int keyB = (startB + k / 2 - 1 < B.length)
                    ? B[startB + k / 2 - 1]
                    : Integer.MAX_VALUE;
        if(keyA < keyB){
            return findKth(A, startA + k / 2, B, startB, k - k / 2);
        } else {
            return findKth(A, startA, B, startB + k / 2, k - k / 2);
        }
    }
}

(F) Median of K sorted arrays

http://stackoverflow.com/questions/6182488/median-of-5-sorted-arrays

其实这个博客里解 median of Two sorted array 的思路更适合解这个 k 的情况，因为这个做法更像图里的 order statistics:

http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html

这题比较简单的使用 heap 的解法也可以用类似于 Kth Smallest Element in a Sorted Matrix 的 minHeap 做法；自定义一个 Tuple，存有 x, y 和 val 信息并根据 val 值 implement comparable interface，相当于在 m 个排序数组里面找 kth smallest number.

时间复杂度：m 个数组，假如每个数组元素平均为 n，总共有 m*n 个元素，中位数要找 mn/2 小的元素，heap size 最大为 m

因此 O(mn * log(m))