LeetCode 0004 - Median of Two Sorted Arrays
# Hints
- 思维 + 二分查找
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Hard |
There are two sorted arrays nums1
and nums2
of size and respectively.
Find the median of the two sorted arrays. The overall run time complexity should be .
You may assume nums1
and nums2
cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3) / 2 = 2.5
# 题意
给定两个升序排列的数组 nums1
and nums2
,大小分别为 和 ,求两个数组中的所有数的中位数。
# 题解
为便于描述,记 nums1
和 nums2
为 和 。
在有序序列中进行查找操作,很容易想到二分查找,然而问题中存在两个序列,虽然问题的单调性是显然的,但是我们却难以直接进行二分。
我们考虑中位数的性质。不妨设 为奇数,显然,比中位数小的数有 个,算上中位数自己就一共有 个,而这些数有些来自于 、有些来自于 。不妨设这些数中有 个来自于 、有 个来自于 ,这意味着我们可以将 和 各自划分为两个部分:
的左部包括 ,右部包括 ;
的左部包括 ,右部包括 ;
我们知道 ,那么对于给定的 ,我们显然可以得出唯一合法的 。
当然,我们也可以将中位数归入右部,那么 ,这并不重要。
注意,由于 ,当 时 可能为负,此时我们不妨交换 和 ,显然不会影响答案,且可以简化问题的求解过程。
此时我们已经成功地将两个变量 转化为了一个变量 ,现在我们就可以像往常那样二分查找了。
因为我们规定比中位数小的数都在左部、比中位数大的数都在右部,因此有 。而 和 显然成立,因此只要 和 成立,就说明找到了正确的划分,中位数即为 。
最后我们考虑具体的二分条件,事实上前面的问题都解决后,这部分是最简单的,稍加思考即可。
当 时,说明 的值太大,应使 减小,且 会随之增大。
当 时,说明 的值太小,应使 增大,且 会随之减小。
当 且 时,求解完成。
不要忘了处理 为偶数的情形,这很简单,因而不再赘述。注意可以利用除法下取整的特性简化代码实现,不必为奇数和偶数分别写出 的不同表达式。
总的时间复杂度为 。
# AC代码
class Solution {
public:
const double INF = 1e9;
public:
double findMedianSortedArrays(vector<int> & nums1, vector<int> & nums2) {
// 特判
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
// 初始化
int m = nums1.size(), n = nums2.size();
// 主循环
double res = 0;
int left = 0, right = m;
while (left <= right) {
// 二分
int i = (left + right) / 2;
int j = (m + n) / 2 - i;
// check
if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
right = i - 1;
} else if (j > 0 && i < m && nums2[j - 1] > nums1[i]) {
left = i + 1;
} else {
double lmax = max((i == 0 ? -INF : nums1[i - 1]), (j == 0 ? -INF : nums2[j - 1]));
double rmin = min((i == m ? INF : nums1[i]), (j == n ? INF : nums2[j]));
if ((m + n) % 2) {
res = rmin;
} else {
res = (lmax + rmin) / 2;
}
break;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01