LeetCode刷题 - 寻找两个有序数组的中位数
题目
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。
思路
竟然要求时间复杂度是O(log(m + n))，我能做出来就不错了，还要求这么高，要啥自行车啊，但是不管怎么样吧，先搞出来在说。至于时间复杂度，一步一步来吧。
解法一
首先我想的就是通过两个 index ，把两个数组合并成一个，然后取出来中间的一位或者两位，就是这个中位数。但是一想，其实没必要全部合并，只需要合并一半即可，虽然思路是正确的，可是最后却怎么也没写出来，总是有这样那样的问题，然后看解析，一个哥们和我是同样的思路，就搬了过来，
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length = nums1.length + nums2.length;
int mid = length / 2;
int left = -1;
int right = -1;
int aStart = 0;
int bStart = 0;
for (int i = 0; i <= mid; i++) {
//保存前一个数据
left = right;
//right始终取的就是两个数组中最小的那个，
if (aStart < nums1.length && (bStart >= nums2.length || nums1[aStart] < nums2[bStart])) {
right = nums1[aStart];
aStart++;
} else {
right = nums2[bStart];
bStart++;
}
}
if (length % 2 == 0) {
return (left + right) / 2.0;
} else {
return right;
}
}
- 用的两个 index ， aStart , bStart ,分别指向两个数组，
- 设置两个变量，用来存中间的两位
- 通过一个 for 循环，两个数组长度一半+1的长度，遍历两个数组，每次都是取个数组中最小的那个，然后index++;
- 如果长度是偶数，就是这两个变量平均数，如果是奇数，是这右侧变量的值。
学习的知识点：
之前我用了大量的代码处理边界的问题，是不是其中某个数组 num1 已经到底了，如果是的话，返回 num2 的值，如果不是，是不是 num2 到底了，如果是，返回 num1 的值，如果都没到边界，判断大小等等一系列的判断，结果人家竟然又一句话就搞定了
aStart < nums1.length && (bStart >= nums2.length || nums1[aStart] < nums2[bStart])
- aStart < nums1.length 说明数组 nums1 没到底，
-
bStart >= nums2.length nums1[aStart] < nums2[bStart] - bStart >= nums2.length 说明数组 num2 到底了， 那么就返回 nums1 的值
- nums1[aStart] < nums2[bStart] 返回最小的值，也就是 nums1 的值
满足条件一和二，就可以认为是返回 nums1 的值，否则就返回 nums2 的值。有点意思，记下了。 人家竟然能想出这么多方法，可是我想出来一个，却还没实现，代码写的不少，却总还是有问题，得好好练习才行
这个时间复杂度是O(m + n)。那O(log(m + n)) 的是什么样的呢，
解法二
其实看到O(log(m + n)) ,就应该的想起来递归，因为递归的时间复杂度就是O(log(n))的，但是却还是想不起来。可是牛人还是有的，一个哥们的代码,使用递归完美解决。而且这个还能处理另外一个问题，求两个有序数组的第 k 个数，如果 k 是中间值的时候，那么就是该问题的解。源码如下
public double 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 个数字
double 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)
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);
}
注释写的很清楚了，递归，我就想起来了之前看《数据结构与算法之美》的时候说的递归的三个条件
- 一个问题可以分解为多个子问题的解
- 这个问题分解后的子问题，除了数据规模之外，求解思路都是一样的
- 存在递归终止条件
那么这个问题能分为多个子问题的解吗？
可以，分别求出 num1 , num2 两个数组的第k/2个元素的值 a , b ，然后判断 a 和 b 的大小，如果 a 大，则说明第 k 个元素在 num1 的[0,k/2]之间或者 num2 的[k/2,num2.length]之间，这样就排除了一半的元素，然后继续。执行这个方法，不过参数变化， num1 和 num2 的起始位置都需要变化，k的值也需要变化。第一次的时候是 k ,第二次的时候，因为已经排除掉了一半，那么 k 的值也需要减小一半，即k-k/2 这样除了数据规模之外，其他思路也都是一样的。条件二也满足了。
那条件三 终止条件呢？
肯定会有一个数组首先到头，那么就返回另外一个数组中第 k 个元素的值
路漫漫其修远兮，吾将上下而刷题。
—
搬运地址：
既已览卷至此，何不品评一二：