题目链接 Leetcode 4. Median of Two Sorted Arrays
题目描述很简单，就是找到两个有序数组合并后的中位数，要求时间复杂度O(log (m+n))。
如果不要去时间复杂度，很容易就想到了归并排序，归并排序的时间复杂度是O(m+n)，空间复杂度也是O(m+n)，不满足题目要求，其实我开始也不知道怎么做，后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
代码如下：
class Solution { private int getkth(int[] A, int as, int[] B, int bs, int k) { if (as > A.length - 1) return B[bs + k - 1]; if (bs > B.length - 1) return A[as + k - 1]; if (k == 1) return Math.min(A[as], B[bs]); int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE; if (as + k/2 - 1 < A.length) aMid = A[as + k/2 - 1]; if (bs + k/2 - 1 < B.length) bMid = B[bs + k/2 - 1]; if (aMid < bMid) return getkth(A, as + k/2, B, bs, k - k/2); else return getkth(A, as, B, bs + k/2, k - k/2); } public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int l = (m + n + 1) / 2; int r = (m + n + 2) / 2; return (getkth(nums1, 0, nums2, 0, l) + getkth(nums1, 0, nums2, 0, r)) / 2.0; } }
