1.题目描述
给定两个大小为 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
2.思路分析
1.首先求中位数：如果是奇数：k/2+1,如果是偶数：(k/2+k/2+1)/2。数组从零开始所以要往前移一位，且要以float类型输出。
2.最先想到的方法：归并排序？排成一个有序的数组，从而求得。
时间复杂度：遍历全部数组 O(m+n)
空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)
3.时间复杂度都达不到题目的要求 O(log(m+n)。看到 log，很明显，我们只有用到二分的方法才能达到。我们不妨用另一种思路，题目是求中位数，其实就是求第(m+n)/2小数的一种特殊情况。
=====>求两个有序数组的第K个数
如图两个数组，假设我们要找第 7 小的数字。
示例
我们比较两个数组的第 k/2 个数字，如果 k 是奇数，向下取整。也就是比较第 3个数字，上边数组中的 4和下边数组中的3，如果哪个小，就表明该数组的前 k/2 个数字都不是第 k 小数字，所以可以排除。也就是 1，2，3 这三个数字不可能是第 7 小的数字，我们可以把它排除掉。将 1349和 45678910 两个数组作为新的数组进行比较。
依次递归~
出口的条件是：
①有一个数组为空
②所求得第k个值为1，则返回两个数组最小的元素
3.代码实现
暴力：归并排序
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums;
int m = nums1.length;
int n = nums2.length;
nums = new int[m + n];
if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
}
if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}
int count = 0;
int i = 0, j = 0;
while (count != (m + n)) {
if (i == m) {
while (j != n) {
nums[count++] = nums2[j++];
}
break;
}
if (j == n) {
while (i != m) {
nums[count++] = nums1[i++];
}
break;
}
if (nums1[i] < nums2[j]) {
nums[count++] = nums1[i++];
} else {
nums[count++] = nums2[j++];
}
}
if (count % 2 == 0) {
return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
} else {
return nums[count / 2];
}
}
二分法
public float findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;
// 处理任何一个nums为空数组的情况
if (m == 0) {
if (n % 2 != 0)
return 1.0 * nums2[n / 2];
return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
}
if (n == 0) {
if (m % 2 != 0)
return 1.0 * nums1[m / 2];
return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
}
int total = m + n;
// 总数为奇数，找第 total / 2 + 1 个数
if ((total & 1) == 1) {
return find_kth(nums1, 0, nums2, 0, total / 2 + 1);
}
// 总数为偶数，找第 total / 2 个数和第total / 2 + 1个数的平均值
return (find_kth(nums1, 0, nums2, 0, total / 2) + find_kth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
}
// 寻找a 和 b 数组中，第k个数字
float find_kth(int[] a, int a_begin, int[] b, int b_begin, int k) {
// 当a 或 b 超过数组长度，则第k个数为另外一个数组第k个数
if (a_begin >= a.length)
return b[b_begin + k - 1];
if (b_begin >= b.length)
return a[a_begin + k - 1];
// k为1时，两数组最小的那个为第一个数
if (k == 1)
return Math.min(a[a_begin], b[b_begin]);
int mid_a = Integer.MAX_VALUE;
int mid_b = Integer.MAX_VALUE;
// mid_a / mid_b 分别表示 a数组、b数组中第 k / 2 个数
if (a_begin + k / 2 - 1 < a.length)
mid_a = a[a_begin + k / 2 - 1];
if (b_begin + k / 2 - 1 < b.length)
mid_b = b[b_begin + k / 2 - 1];
// 如果a数组的第 k / 2 个数小于b数组的第 k / 2 个数，表示总的第 k 个数位于 a的第k / 2个数的后半段，或者是b的第 k
// / 2个数的前半段
// 由于范围缩小了 k / 2 个数，此时总的第 k 个数实际上等于新的范围内的第 k - k / 2个数，依次递归
if (mid_a < mid_b)
//这里第二次递归时，k=k-k/2;不能是k=k/2,因为我们只是排除前面的k/2个
return find_kth(a, a_begin + k / 2, b, b_begin, k - k / 2);
// 否则相反
return find_kth(a, a_begin, b, b_begin + k / 2, k - k / 2);
}
