4-寻找两个有序数组的中位数
@Author：CSU张扬
@Email：csuzhangyang@gmail.com or csuzhangyang@qq.com
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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
2. 解法
2.1 解法一：归并排序
将两个数组进行归并排序，从小到大依次存入vector中。取中位数即可。
执行用时: 24 ms, 在所有 cpp 提交中击败了76.59%的用户
内存消耗: 11.3 MB, 在所有 cpp 提交中击败了72.07%的用户
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<double> v;
int i1 = 0, i2 = 0;
while(i1 != nums1.size() && i2 != nums2.size()) {
if (nums1[i1] <= nums2[i2]) {
v.push_back(nums1[i1]);
++ i1;
}
else {
v.push_back(nums2[i2]);
++ i2;
}
}
if (i1 != nums1.size()) {
for (i1; i1 < nums1.size(); ++ i1)
v.push_back(nums1[i1]);
}
else {
for (i2; i2 < nums2.size(); ++ i2)
v.push_back(nums2[i2]);
}
if ((nums1.size() + nums2.size())%2)
return v[(nums1.size() + nums2.size())/2];
else
return (v[(nums1.size() + nums2.size())/2] + v[(nums1.size() + nums2.size())/2 - 1]) / 2;
}
};
2.2 解法二：递归二分法
- 题目要求复杂度为O(log(m+n))，所以肯定要使用二分法。
- 同时我们可以将题目转化为求第k个最小数，即
k=(m+n)/2； - 对两个序列的第
k/2个值进行比较，若nums1[k] > nums2[k]，则nums2的前k/2个数中肯定没有我们要求的第k个最小数。我们将前nums2中前k/2个数剔除。 - 对新序列的nums1和nums2继续进行求第
k1(此时k1=k-k/2)个最小数。 - 当然我们会遇到一些特殊情况，比如某序列太短，例如
(nums1.size() < nums2.size())，此时肯定是nums1可能会出现没有第k/2个数（nums2不会出现这种情况），此时替换为该序列的最后一个值即可。为了简化代码，如果(nums1.size() > nums2.size())，我们就递归函数getKthElem重新传参，将参数调换（即nums1 <-> nums2等）。 - 由此产生的另外一种需要考虑的问题是，步骤4中的
k1=k-k/2是否完全正确？我们每次剔除的元素该不该是k/2个？ 当然不一定，因为有的序列可能没有那么多元素，这时我们需要令k=k-我们剔除的数，即：k=k-min(k/2,len)。在代码中我们不能将 min函数 作为一个参数，因为我们定义了int i = start1 + min(k / 2, len1) - 1, 在实际代码中我们使用(j - start2 + 1)来替代它。 - 那么问题来了，6中这种替换是正确的吗？ 其实这种替换是无妨的，因为们剔除的元素始终小于k/2个，当
len < k/2时，剔除了len个元素，我们此时只是不是严格的二分了。我们每次少剔除几个元素在逻辑上是没有问题的（当然多的话就会有问题），因为在k/2前的这几个元素肯定不是我们要找的第k个最小数。 - 递归函数什么时候结束呢？ 两种情况：一是某个序列的长度变为了0，那么我们只需在另一个序列中找第k个最小数即可；二是
k=1时，此时找的是两个序列的第1个最小值，那么就是两个序列第一个元素较小的那个。
执行用时: 8 ms, 在所有 cpp 提交中击败了99.98%的用户
内存消耗: 9.7 MB, 在所有 cpp 提交中击败了86.47%的用户
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size();
int n = nums2.size();
int k = (m + n) / 2;
if ((m + n) % 2)
return getKthElem(nums1, 0, m - 1, nums2, 0, n - 1, k + 1);
else
return (getKthElem(nums1, 0, m - 1, nums2, 0, n - 1, k) + getKthElem(nums1, 0, m - 1, nums2, 0, n - 1, k + 1)) * 0.5;
}
int getKthElem(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2)
return getKthElem(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0)
return nums2[start2 + k - 1];
if (k == 1)
return min(nums1[start1], nums2[start2]);
int i = start1 + min(k / 2, len1) - 1;
int j = start2 + min(k / 2, len2) - 1;
if (nums1[i] > nums2[j])
// 注意：(j - start2 + 1) = min(k / 2, len1)
// 但是我们不能将min函数作为参数。
return getKthElem(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
else
return getKthElem(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
// 参考https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/
};