作者：Grey
原文地址：寻找两个正序数组中的中位数
题目链接
例如：nums1数组是 [1,2], nums2 数组是 [3,4]
那么这两个数组的合并数组是[1,2,3,4] ，所以中位数 (2 + 3) / 2 = 2.5
再比如：nums1数组是 [1,2,3], nums2 数组是 [4,5]
那么这两个数组的合并数组是[1,2,3,4,5] ，所以中位数 3
时间和空间都是O(M+N)的解法
这不是最优解，但是是最容易想到的一个解法，即，创建一个合并数组，这个数据的长度就是两个数据长度之和，然后通过合并有序数组的方法将这个合并数组生成出来，如果合并数组长度是奇数，则取中间值，如果合并长度是偶数，则取上中位数和下中位数，通过（上中位数+下中位数）/ 2 得到结果。
这个解法的时间复杂度和空间复杂度都是O(M+N), 比较简单，完整代码如下：
public double findMedianSortedArrays1(int[] nums1, int[] nums2) { // 题目已经说明nums1和nums2不能同时为空 if (null == nums1 || nums1.length == 0) { return median(nums2); } if (null == nums2 || nums2.length == 0) { return median(nums1); } int m = nums1.length; int n = nums2.length; int[] nums = new int[m + n]; int i = 0; int j = 0; int index = 0; // 合并两个有序数组的实现 while (i < m && j < n) { if (nums1[i] >= nums2[j]) { nums[index++] = nums2[j++]; } else { nums[index++] = nums1[i++]; } } while (i < m) { nums[index++] = nums1[i++]; } while (j < n) { nums[index++] = nums2[j++]; } return median(nums); } // 求一个有序数组的中位数 // 如果是奇数，直接返回中间位置的值 // 如果是偶数，则返回（上中位数+下中位数）/ 2的值 public static double median(int[] arr) { int len = arr.length; if ((len & 1) == 1) { // 奇数 return arr[len / 2]; } return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d); } 时间复杂度O(log(M+N))的解法
如果我们可以高效实现如下方法：
// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么 int findKth(int[] nums1, int[] nums2, int k) 那么题目就可以通过如下方式实现：
public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 题目已经说明nums1和nums2不能同时为空 if (null == nums1 || nums1.length == 0) { return median(nums2); } if (null == nums2 || nums2.length == 0) { return median(nums1); } int m = nums1.length; int n = nums2.length; if (((m + n) & 1) == 1) { // 合并后的数组长度是奇数，则取中间这个数 return findKth(nums1, nums2, (m + n) / 2 + 1); } // 合并后的数组长度如果是偶数，则返回（上中位数+下中位数）/ 2的值 return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d; } 现在所有的目光都聚焦在这个算法中，
// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么 int findKth(int[] nums1, int[] nums2, int k) 注：以上算法中，我们规定k以1开始计算，也就是说：合并数组中最小的数是第1小的，而不是第0小的。且在调用的时候，保证1<= k <= nums1.lengh + nums2.length。
在解决这个算法之前，假设我们已经有一个方法，可以高效得到：两个长度相等的排序数组合并后的上中位数，我们假设这个方法为：
// 获取两个长度相等的有序数组merge后的上中位数 // 如果是偶数，取上中位数 // 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长 int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) 一旦我们有getUpMedian这个方法，我们就可以针对k的取值，分多种情况来解决findKth方法，我们假设
int findKth(int[] nums1, int[] nums2, int k) 方法中，较长的数组我们重新定义为名字为longs的数组，较短的数组重新定义为名字shorts的数组。
现在开始讨论k的范围：
第一种情况：k<=shorts.length
在这种情况下比较简单，我们可以将longs数组取前k个数，shorts数组取前k个数，然后调用getMedian方法，拿到中位数，即是longs和shorts数组合并后的第k小的数。
例如：shorts数组为[1,3,5,7]，longs数组为[2,4,6,8,10,12]
如果要取第2小的数, 客观上第2小的数是2，可能存在的范围是shorts的前2个数中，也可能存在在longs的前2个数中，除此之外，不能是其他范围，因为超过这个范围，就不止第2小了。
第二种情况：shorts.length<k<=longs.length
在这种情况下，shorts数组中的每个数都有可能，longs数组可以排除掉 前(k – shorts.len – 1) 个数，以及[kth + 1……longs.length]区间的所有数，但是要手动验证一下long中第(k- shorts.len)位置上的数是不是比shorts最后一个数大，
如果是，longs中第(k – shorts.length)位置上的数即为第k小的数,
如果不是，longs中第(k – shorts.length)位置上的数直接排除掉,
longs中剩余数和shorts中所有数用一次getUpMedian方法求得的值即为第k小的数。
例如：shorts数组为[1,3,5,7]，longs数组为[2,4,6,8,10,12,14,16,18]
求第7小的数，此时shorts中的数都有可能是第7小的数，但是，longs中，可以排除如下位置的数
首先：从第8小的数开始一直到第longs.length小的数都可以排除。
其次， 7 – shorts.length – 1 即：7 – 4 – 1 = 3 ，longs中第3小之前的数都可以排除，
排除完毕后，验证一下longs中第3小的数是不是比shorts中最后一个数大，如果是，则longs中第3小的数即位两个数组的第7小的数。
如果不是，则longs中剩余可选的数继续和shorts调用getUpMedian方法。
第三种情况：longs.length<=k<=(shorts.length+longs.length)
这种情况下，shorts中可排除掉前面(k – longs.length)个数，longs中排除掉前( k – shorts.length – 1) 个数，然后手动判断下shorts和longs中剩余数中最左边的数是不是第k小的数，如果是，直接返回，如果不是，排除掉这些数，然后将shorts和longs剩余数用getUpMedian获取的结果即为答案。
例如：shorts数组为 [1,3,5,7,9,11] 长度是6，longs数组为 [2,4,6,8,10,12,14,16,18,20,22,24] 长度是12，假设要求第15小的数，那么在shorts中可以排除掉前面（15 – longs.length – 1）= 2个数， 因为即便shorts中第1小的数比longs中所有数都大，它也只能算第13小的数，第2小的数即便比longs中所有数都大，也只能算全局第14小的数。longs中可以排除掉第1一直到第8小（即：15 – shorts.length – 1 = 8）的数，因为longs中第8小的数即便比shorts数所有数都大，也只能是全局第14小的数。经过排除后，shorts中和longs中可选范围为（以下数组中没打x的数字）
shorts中为[x,x,5,7,9,11]
longs中为[x,x,x,x,x,x,x,x,18,20,22,24]
先手动判断一下，longs中的18和shorts中的5是否是第15小的数，如果是则直接返回，如果不是，shorts中[7,9,11] 和 longs中 [20,22,24] 使用getUpMedian获取的结果即为答案。
所有情况说明完毕，而且三种情况仅依赖getUpMedian 方法。所以，现在看getUpMedian 方法的实现，具体说明见注释：
// 获取两个长度相等的有序数组merge后的上中位数 // 如果是偶数，取上中位数 // 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长 public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) { if (s1 == e1) { // 说明A和B分别只有一个数，因为求上中位数，所以取A[s1]和B[s2]的最小值 return Math.min(A[s1], B[s2]); } int mid1 = (s1 + e1) / 2; int mid2 = (s2 + e2) / 2; // 如果A和B的中位数值一样，则这个中位数值也是A和B合并后的中位数值 if (A[mid1] == B[mid2]) { return A[mid1]; } boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数 if (even) { // 通过类似二分的方式，判断A和B的中位数可能出现的位置， if (A[mid1] > B[mid2]) { // 如果A[mid1] > B[mid2] // 则全局的中位数只可能在A的[s1..mid1]以及B的[mid2+1..e2]范围内产生 // 下面的判断类似。 return getUpMedian(A, s1, mid1, B, mid2 + 1, e2); } else { return getUpMedian(A, mid1 + 1, e1, B, s2, mid2); } } else { if (A[mid1] > B[mid2]) { if (B[mid2] > A[mid1 - 1]) { return B[mid2]; } return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2); } else { if (A[mid1] > B[mid2 - 1]) { return A[mid1]; } return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1); } } } getUpMedian通过类似二分查找的方法，来得到中位数信息，复杂度就是O(log(M+N))。完整代码见：
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 题目已经说明nums1和nums2不能同时为空 if (null == nums1 || nums1.length == 0) { return median(nums2); } if (null == nums2 || nums2.length == 0) { return median(nums1); } int m = nums1.length; int n = nums2.length; if (((m + n) & 1) == 1) { return findKth(nums1, nums2, (m + n) / 2 + 1); } return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d; } public static double median(int[] arr) { int len = arr.length; if ((len & 1) == 1) { // 奇数 return arr[len / 2]; } return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d); } public static int findKth(int[] nums1, int[] nums2, int k) { int[] longs = nums1.length > nums2.length ? nums1 : nums2; int[] shorts = nums1 == longs ? nums2 : nums1; int maxLen = longs.length; int minLen = shorts.length; // k<= minLen // longs截取前k个数，shorts截取前k个数，两个长度相等的数组取上中位数 if (k <= minLen) { return getUpMedian(shorts, 0, k - 1, longs, 0, k - 1); } // k > minLen 且 k <= maxLen // 到这里一定k > minLen if (k <= maxLen) { // 可以排除 // longs中比第k小的数还大的所有数都可以排除，即下标为：[k....maxLen - 1] // longs中第1小到第(k - minLen - 1)小的数都可以排除 // shorts中所有数都有可能 // 手动验证 // longs中第 (k - minLen) 大的数是否比shorts中最后一个数大，如果是，这个数直接就是结果 if (longs[k - minLen - 1] >= shorts[minLen - 1]) { return longs[k - minLen - 1]; } // 其他的数 return getUpMedian(shorts, 0, minLen - 1, longs, k - minLen, k - 1); } // k > maxLen 且 k <= maxLen + minLen // 到这里一定 k > maxLen 且 k <= maxLen + minLen // 可以排除 // shorts中从第1小一直到第k - maxLen - 1小的数都可以排除 // longs中第1小的数一直到第k - minLen - 1小的数都可以排除 // 手动验证 if (shorts[minLen - 1] <= longs[k - minLen - 1]) { return longs[k - minLen - 1]; } if (longs[maxLen - 1] <= shorts[k - maxLen - 1]) { return shorts[k - maxLen - 1]; } // 其他的数 return getUpMedian(shorts, k - maxLen, minLen - 1, longs, k - minLen, maxLen - 1); } public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) { if (s1 == e1) { return Math.min(A[s1], B[s2]); } int mid1 = (s1 + e1) / 2; int mid2 = (s2 + e2) / 2; if (A[mid1] == B[mid2]) { return A[mid1]; } boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数 if (even) { if (A[mid1] > B[mid2]) { return getUpMedian(A, s1, mid1, B, mid2 + 1, e2); } else { return getUpMedian(A, mid1 + 1, e1, B, s2, mid2); } } else { if (A[mid1] > B[mid2]) { if (B[mid2] > A[mid1 - 1]) { return B[mid2]; } return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2); } else { if (A[mid1] > B[mid2 - 1]) { return A[mid1]; } return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1); } } } } 
