题目描述
给定两个大小为 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
题目解析
解决这个问题,我们必须要搞清楚两个问题:
- 两个数组都是有序数组,数组的元素都是从小到大排列的
- 中位数的定义:在中学数学中,我们可能学习过中位数的定义,但在统计学中,中位数还有这样一种解释:
中位数:当一个数可以将一个集合划分成两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素,那么这个数就称为集合的中位数。
这个题目的难点在于,给你一个有序数组,你肯定会求中位数。给你两个数组,你肯定也能想办法用暴力法解出来,但暴力求解,复杂度一定是超过的!
这个题目是查找两个有序数组的中位数,我们能想到的级别的查找算法,恐怕只有二分查找了。
二分查找法是用于解决一个数组的查找问题的,那么如何解决两个数组的问题呢?还是有一些情况需要讨论!
解法:二分查找法
从前面中卫数的定义来看,我们的出发点,应该是划分而不是遍历。
那么具体应怎么划分呢?假设有两个有序数组A、B,长度分别为m、n:
首先,让我们在任一位置 将 划分成两个部分(注意A[i]
在右边这个集合):
left_A | right_A
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
不难得出:
同样我们在位置 对 进行划分:
left_B | right_B
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
同理:
将两个数组的左右部分都合并起来,形成总体的两个左右子集:
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
如果i
和j
的取值足够合适,使得:
那么我们就可以找到这个中位数,它就等于:
上面的两个条件,等价于:
这里有几点需要说明:
这里我们假设始终存在,也就是说, 这种极端情况我们最后来讨论
这里设,因为都必须是非负数,且, 当时,左边的表达式有可能小于0
条件2中的两个子条件,不可能同时不满足,请自己思考原因
所以,我们的任务就是:
在中搜索 ,使得, 其中
现在,我们已经把一个双数组遍历问题,变成了对一个变量的搜索问题!
接下来,我们来具体设计我们的二分算法:
设,它们夹成了一个 的初始搜索区间
在二分查找法中,被查找的 应该赋予这个区间的中值,即, 那么 也可以根据求得一个值
-
现在我们来检查上面的条件2是否满足,一共有3种情况:
这表明 已经搜索到了目标值,结束搜索
:这意味着 太小了,目标值应该在之间,因此设,返回步骤2
:这意味着 太大了,目标值应该在之间,因此设,返回步骤2
最后,我们来讨论一下刚才忽略的临界情况:
这里我们要证明一下 与 的取值关系
由于,
, 当且仅当时,
同理可证, 当且仅当时,
这意味着,在判断临界情况时,我们只需关心 的取值, 为临界值, 也一定取临界值
还意味着,必然有一个是存在的,也必然有一个是存在的!
还没完!
现在我们只是找到了最佳划分,还没有搞清楚哪个值是中位数!
现在,我们已经把A和B划分成了合适的left_part和right_part两个子集
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[n-1]
那么,中位数只能在和中产生
由于,且在C++中,整数除法会舍弃小数,向下取整。
-
当为奇数的时候,虽然我们的条件使得,但由于C++向下取整的特性,两边长度的条件并不会成立,实际上某一部分会比另一个部分多出一个元素。多出的那个元素,就是我们要找的中位数。
C++的特性,实际上是缩小了 的取值, 的取值也会在循环中间接缩小一点,所以中位数一定是在right_part里面!
即:
当为偶数,就很容易了,
至此,我们需要讨论的点已经全部清楚了,怎么样,这就是LeetCode的“魅力”!
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int m = nums1.size();
const int n = nums2.size();
if(m > n) return findMedianSortedArrays(nums2, nums1);//我们是假设n>=m的
const int k = (m + n) / 2;
int imin = 0;
int imax = m;
while(imin <= imax){
int i = (imin + imax) / 2;
int j = (k-i);
if (i < imax && nums2[j-1] > nums1[i]){
imin = i + 1; // i 太小了
}
else if (i > imin && nums1[i-1] > nums2[j]) {
imax = i - 1; // i 太大了
}
else{
//此时i刚刚好
//我们用INT_MIN, INT_MAX(相当于无穷小和无穷大)来代替不存在的情况
int maxLeft = max(i <= 0 ? INT_MIN : nums1[i-1],
j <= 0 ? INT_MIN : nums2[j-1]);
if((m + n) % 2 == 1)
return maxLeft;
int minRight = min(i >= m ? INT_MAX: nums1[i],
j >= n ? INT_MAX : nums2[j]);
return (maxLeft + minRight) * 0.5;
}
}
return 0.0;
}
};
复杂度分析
- 时间复杂度:,因为查找的空间每次都会缩短为原来的一半,且这个空间的初始长度取决于m, n的最小值
- 空间复杂度:我们只使用了一些局部变量,没有引入新的内存来存放数组