**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
这道题在算keyA和keyB的时候不用考虑k的奇偶性. 都按k/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.+