04.寻找两个有序数组的中位数（难度：困难）
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解法一：
这道题是求两个有序数组的中位数，如果不限制时间复杂度的话，那么这道题将会无比简单。
把长度为m和长度为n的两个数组的数据放在一个新的数组中，然后对数组进行排序，找到中位数。
找中位数的时候，因为组合后的数组元素个数(m + n)的奇偶性不确定，如果是奇数的话，那么中位数就是第（m+n）/ 2 个元素，如果是偶数的话，那么中位数就是第（m + n ）/ 2 个元素和第（m + n）/ 2 + 1个。
我们可以利用int整型向下取整的特点，把上面两种情况归结为一种通用的解法，我们可以找到下标（m + n - 1）/ 2和下标（m + n ）/ 2元素，然后求两数的平均值。
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int [] result = Arrays.copyOf(nums1, nums1.length + nums2.length);
System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
Arrays.sort(result);
double d = (double)(result[(nums1.length + nums2.length -1)/2] + result[(nums1.length + nums2.length )/2])/2;
return d;
}
执行用时 :4 ms, 在所有 Java 提交中击败了31.34%的用户
内存消耗 :42.2 MB, 在所有 Java 提交中击败了96.67%的用户
上述的关键代码虽然只有4行，但是在时间复杂度上是不满足题目要求的。
解法二：
看见时间复杂度的限制O(log(m+n))，肯定要用二分查找法来解决，其次，中位数的应在的位置依旧按照解法一的方法，不过这次我们不合并数组了，这样会增加时间复杂度。
找中位数的时候，因为两个数组的元素个数之和(m + n)的奇偶性不确定，如果是奇数的话，那么中位数就是第（m+n）/ 2 个元素，如果是偶数的话，那么中位数就是第（m + n +1 ）/ 2 个元素和第（m + n +2）/ 2 个。
下来我们着重看看，如何在两个有序数组中找到第k个元素：
首先，我们利用i和j分别标记数组nums1和 nums2的起始位置，
此次我们处理一些边界问题：
（1）当一个数组的起始位置大于等于该数组的长度，表明该数组所有的数字都已经被淘汰了，相当于空数组，那么我们只需要继续在另一个数组里面找，直接可以找出来。
（2）当k = 1的时候，我们只需要比较两个有序数组的起始位置i和j 的数字就好。
难点在于如何处理一般情况？
为了加快搜索速度，我们使用二分法：
（1）我们可以先对k二分，意思就是去找到nums1和nums2的第k/2个数字。
（2）因为两个数字的长度不定，所有我们需要先判断一下两个数组是否都含有第k/2个数字，如果存在就取出来，如果不存在就给它赋一个最大值，赋最大值的原因是：我们后面会通过比较两个数组中取出来的数字，如果小的那个数组，那么前k/2个元素里面必然不会有中位数，那么我们就可以把它舍去。
（3）那么会不会两个数组都不存在第k/2个元素，在这道题里面是不可能的，因为k是m+n的中间值，所以至少也会有一个数组中有第k/2个元素。
（4）最后就是二分法的核心，而是递归的重点。我们比较两个数组的第k/2小的元素值mid1和mid2，如果nums1的mid1小的话，那么说明中位数肯定不住nums1数组的前k/2中，我们就可以把第一个数组的前k/2个数字淘汰，将nums1的起始位置i向后移动k/2个，并且让k也减去k/2，调用递归。反之，如果是nums2的mid2小的话，那么我们就淘汰nums2的前k/2个元素，并且让k减去k/2，调用递归。
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0;
}
public static int find(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length)
return nums2[j + k - 1]; // nums1数组全部被舍弃
if (j >= nums2.length)
return nums1[i + k - 1]; // nums2数组全部被舍弃
// 当k = 1 的时候，两个数组的布局基本相同，最后只需要找到
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
int mid1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int mid2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return find(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return find(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
测试类
package com.company.project.hot100;
import java.util.Arrays;
public class Question04 {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] result = Arrays.copyOf(nums1, nums1.length + nums2.length);
System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
Arrays.sort(result);
double d = (double) (result[(nums1.length + nums2.length - 1) / 2] + result[(nums1.length + nums2.length) / 2])
/ 2;
return d;
}
public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
if (nums1.length < 2 && nums2.length < 2) {
if (nums1.length == 0) {
return (double) nums2[0];
} else if (nums2.length == 0) {
return (double) nums1[0];
}
return (double) (nums1[0] + nums2[0]) / 2;
}
int[] result = Arrays.copyOf(nums1, nums1.length + nums2.length);
System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
Arrays.sort(result);
int mid = result.length >> 1;
if ((result.length & 1) == 1) {
return (double) result[(result.length - 1) >> 1];
} else {
return (double) (result[mid - 1] + result[mid]) / 2;
}
}
public static double findMedianSortedArrays3(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
int left = (m + n + 1) / 2;
int right = (m + n + 2) / 2;
return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0;
}
public static int find(int[] nums1, int i, int[] nums2, int j, int k) {
if (i >= nums1.length)
return nums2[j + k - 1]; // nums1数组全部被舍弃
if (j >= nums2.length)
return nums1[i + k - 1]; // nums2数组全部被舍弃
// 当k = 1 的时候，两个数组的布局基本相同，最后只需要找到
if (k == 1) {
return Math.min(nums1[i], nums2[j]);
}
int mid1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
int mid2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return find(nums1, i + k / 2, nums2, j, k - k / 2);
} else {
return find(nums1, i, nums2, j + k / 2, k - k / 2);
}
}
public static void main(String[] args) {
int[] nums1 = { 9, 10, 11, 12, 13, 14 };
int[] nums2 = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 };
// int[] nums1 = { 1 };
// int[] nums2 = { 2 };
System.out.println(findMedianSortedArrays3(nums1, nums2));
}
}
