题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数。
算法的时间复杂度应该为 O(log(m+n))。
难度：困难
示例1
输入：nums1 = [1, 3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1, 2, 3]，中位数 2
示例2
输入：nums1 = [1, 2], nums2 = [3, 4]
输出：2.50000
解释：合并数组 = [1, 2, 3, 4]，中位数 (2 + 3) / 2 = 2.5
提示
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-10^6 <= nums1[i], nums2[i] <= 10^6
分析
乍一看，寻找两个正序数组的中位数，一种方法是遍历两个数组，将每个元素按正序放入一个新的大数组中，然后返回中间位置的值即可，时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。
或者是将两个数组合并后再排序，合并数组的时间复杂度为 O(m+n)，排序过程如果用快速排序的话平均时间复杂度为 O((m+n)log(m+n))。
这种方法虽然简单，但是无法满足题目要求的 O(log(m+n)) 的时间复杂度。
我们想一想，两个数组 A 和 B 的中位数，就是他们合并后那个大数组中间位置的数，而且这个大数组是正序的，那么我们可以把问题转化为寻找这个大数组中第 k 位置的数。
如果大数组的长度为奇数，则 k = (m + n) / 2，中位数就是位置为 k 的数；如果长度是偶数，k = (m + n) / 2，中位数是位置为 k 和 k + 1 两个数的平均值。
题目要求时间复杂度为 O(log(m+n))，很像是二分查找的时间复杂度，我们就从这个角度来考虑。
对于这个大数组来说，位置 k = (m + n) / 2 将他分割为左右两部分，左侧元素的数量为 k 个，这 k 个元素必然一部分在数组 A 中，一部分在数组 B 中。假设各占一半，那么就有 k/2 个元素在 A 中，k/2 个元素在 B 中。
我们来比较 A, B 两个数组中这 k/2 个元素中最大的值，也就是位于 k/2 - 1 这个位置的值。
如果 A[k/2 - 1] < B[k/2 - 1]，那么说明在数组 A 中，他的位置 0 到 k/2 - 1 的这些元素，在大数组中都位于中位数的左侧。想象一下，如果在大数组中去除掉这些元素，那么寻找第 k 大的元素这个问题就变成了寻找第 k - k/2 的元素。
好，去除这些元素后，数组 A 变成了他的 k/2 - 1 位置右侧所有元素的子数组，k 变成了 k - k/2，我们要做的就是在这个子数组和数组 B 中，继续寻找第 k 大的元素。
这样每次 k 都会变成他的一半大小，直到最终变成寻找第 0 大或第 1 大的元素，这个时候就很方便的找到了。这样看起来符合题目要求的 O(log(m+n)) 的时间复杂度，我们写代码来实现一下。
解答
import java.util.Arrays;
public class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 奇数，找第 k 个数；偶数，找第 k 个数和第 k+1 个数，计算平均值
int k = (nums1.length + nums2.length) / 2;
boolean isEven = (nums1.length + nums2.length) % 2 == 0;
int offset1 = 0; // 数组 nums1 去除元素后的偏移量
int offset2 = 0; // 数组 nums2 去除元素后的偏移量
while (k > 1) {
// 比较 k/2 - 1 位置的元素
int curIdx = k / 2 - 1;
if (curIdx + offset1 >= nums1.length || curIdx + offset2 >= nums2.length) { // 超出其中一个数组的边界
int[] nums1Remain = Arrays.copyOfRange(nums1, offset1, nums1.length); // nums1 去除部分元素后的子数组
int[] nums2Remain = Arrays.copyOfRange(nums2, offset2, nums2.length); // nums2 去除部分元素后的子数组
return isEven ? (findKthElem(nums1Remain, nums2Remain, k - 1) + findKthElem(nums1Remain, nums2Remain, k)) / 2.0 : findKthElem(nums1Remain, nums2Remain, k);
}
if (nums1[curIdx + offset1] < nums2[curIdx + offset2]) {
offset1 += curIdx + 1; // 增加 nums1 的偏移量，相当于去除了该位置左侧的元素
} else {
offset2 += curIdx + 1; // 增加 nums2 的偏移量，相当于去除了该位置左侧的元素
}
k -= curIdx + 1; // 问题由 寻找第 k 大的值 转为 寻找第 k - k/2 大的元素
}
// 此时中位数左侧的数基本已去除完毕，k = 0 或 k = 1，相当于寻找第 0 大或第 1 大的元素
// 如果大数组长度为偶数，在找到第 k 大的元素后，还需要找到第 k + 1 大的元素，计算二者的平均值
int[] nums1Remain = Arrays.copyOfRange(nums1, offset1, nums1.length);
int[] nums2Remain = Arrays.copyOfRange(nums2, offset2, nums2.length);
return isEven ? (findKthElem(nums1Remain, nums2Remain, k - 1) + findKthElem(nums1Remain, nums2Remain, k)) / 2.0 : findKthElem(nums1Remain, nums2Remain, k);
}
/**
* 辅助函数，寻找两个数组中第 k 大的元素
* @param nums1 数组1
* @param nums2 数组2
* @param k 第 k 大
* @return 找到的元素值
*/
public int findKthElem(int[] nums1, int[] nums2, int k) {
if (nums1.length == 0) return nums2[k]; // 若 nums1 为空，则第 k 大的数就是 nums2 中位置为 k 的元素
if (nums2.length == 0) return nums1[k]; // 若 nums2 为空，则第 k 大的数就是 nums1 中位置为 k 的元素
if (k == 0) return Math.min(nums1[0], nums2[0]); // 第 0 大的数，返回两个数组中的最小值
// 去除两个数组中最小的元素后，相当于寻找第 k - 1 大的元素
if (nums1[0] < nums2[0]) return findKthElem(Arrays.copyOfRange(nums1, 1, nums1.length), nums2, k - 1);
return findKthElem(nums1, Arrays.copyOfRange(nums2, 1, nums2.length), k - 1);
}
public void test1() {
int[] nums1 = {1, 3};
int[] nums2 = {2};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println(result == 2);
}
public void test2() {
int[] nums1 = {1, 2};
int[] nums2 = {3, 4};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println(result == 2.5);
}
public void test3() {
int[] nums1 = {1, 3, 4, 9};
int[] nums2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println(result == 4);
}
public void test4() {
int[] nums1 = {1};
int[] nums2 = {2, 3, 4, 5, 6, 7, 8};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println(result == 4.5);
}
public void test5() {
int[] nums1 = {};
int[] nums2 = {1, 2};
double result = findMedianSortedArrays(nums1, nums2);
System.out.println(result == 1.5);
}
public static void main(String[] args) {
Solution solution = new Solution();
solution.test1();
solution.test2();
solution.test3();
solution.test4();
solution.test5();
}
}
上述代码中还加入了几个测试用例。
个人而言，这种解法很难想明白 :P，我也是看了题解后思考很久才搞懂并写代码实现出来，哈哈。