题目描述
4. Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
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
题意:求两个有序数组的中位数。
算法1
(二分) $O(log(min(n,m)$
题意:求两个有序数组的中位数。
题解1:二分搜索。为了方便讨论我们首先假设两个数组的长度分别为n,m
,并且有n <= m
,并且n + m
是奇数,那么我们要找的数字其实就是两个数组合并后第k = (n + m + 1) / 2
小的数字。我们尝试将两个数组划分成两个部分,A
数组左侧有i
个元素,B
数组左侧有j
个元素,并且i + j = k
。
left_part | right_part
A[0], A[1], ..., A[i-1] | A[i], A[i+1], ..., A[n-1]
B[0], B[1], ..., B[j-1] | B[j], B[j+1], ..., B[m-1]
如果我们能够保证A[i - 1] < B[j] && B[j - 1] < A[i]
,那么说明left_part
中的所有元素都小于right_part
中的元素,并且第k
小的元素就是max(A[i - 1],B[j - 1])
。
如果A[i - 1] > B[j]
说明i
偏大,我们需要将i
缩小尝试得到A[i - 1] < B[j]
。
如果B[j - 1] > A[i]
说明i
偏小,我们需要将i
放大尝试得到B[j - 1] < A[i]
。
那么我们使用二分查找来找到左边放多少个i
数字比较合适,初始搜索区间为[0:n]
,如果左边放置i
个元素,那么右边放置j = k - i
个元素。
接下来我们考虑一些边界条件:
如果i = 0
,相当于最小的k
个数都在B
中,这时整体第k
小的元素就是B[k - 1]
如果j = 0
,相当于最小的k
个数都在A
中,这时整体第k
小的元素就是A[k - 1]
否则,最小的k
个数,i
个在A
中,j
个在B
中,这时整体第k
小的元素就是max(A[i - 1],B[j - 1])
上面我们的讨论,我们是基于n + m
是奇数的,这时候我们只需要找到上述元素就好了,但是当n + m
是偶数的时候,我们还需要找到right_part
中最小的元素,这个值也就是min(A[i],B[j])
,这时候仍然需要讨论一些边界情况:
如果i = n
,那么A
中没有比A[i - 1]
还大的了,那么只能是B[j]
如果j = m
,那么B
中没有比B[j - 1]
还大的了,那么只能是A[i]
否则,整体第k + 1
小的元素就是min(A[i],A[j])
C++ 代码
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(),m = nums2.size();
if(n > m){swap(nums1,nums2),swap(n,m);}
int l = 0,r = n,k = (n + m + 1) >> 1;
while(l <= r)
{
int i = (l + r) >> 1,j = k - i;
if(i < n && nums1[i] < nums2[j - 1] )
l = i + 1;
else if(i > 0 && nums1[i - 1] > nums2[j])
r = i - 1;
else
{
int max_left,min_right;
if(i == 0) max_left = nums2[k - 1];
else if(j == 0) max_left = nums1[k - 1];
else max_left = max(nums1[i - 1],nums2[j - 1]);
if((n + m) % 2 == 1) return max_left;
if(i == n) min_right = nums2[j];
else if(j == m) min_right = nums1[i];
else min_right = min(nums1[i],nums2[j]);
return (max_left + min_right)/2.0;
}
}
return 0.0;
}
算法2
(分治) $O(log(n + m)$
题解2:我们将问题直接转化成求两个数组中第k
小的元素,和题解1类似,只不过这次我们从另一种角度去考虑。
首先我们给出getKthSmallest
函数的参数含义:表示从nums1[i:nums1.size() - 1]
和nums2[j:nums2.size() - 1]
这两个切片中找到第k
小的数字。假设nums1
和nums2
的切片元素个数分别为len1
和len2
,为了方便讨论,我们定义为len1 < len2
。
考虑一般的情况,我们在这两个切片中各取k / 2
个元素,令si = i + k / 2, sj = j + 2 / k
,得到切片nums1[i : si - 1]
和nums2[j : sj - 1]
。
如果nums1[si - 1] < nums2[sj - 1]
说明nums1[i : si - 1]
中的元素都是小于第k
小的元素的,我们可以舍去这部分元素,在剩下的区间内去找第k - k / 2
小的元素。
如果nums1[si - 1] >= nums2[sj - 1]
说明nums2[j : sj - 1]
中的元素都是小于第k
小的元素的,我们可以舍去这部分元素,在剩下的区间内去找第k - k / 2
小的元素。
考虑特殊情况,当nums1[i : nums1.size() - 1]
切片中的元素小于k / 2
个了,那么我们就将这个切片中的所有元素取出来,在nums2
中仍然取k / 2
个元素,这是因为k
是一个有效值即len1 + len2 >= k
,不可能出现len1 < k / 2
的同时len2 < k / 2
;另一方面因为我们确保了len1 < len2
,所以也不可能出现len1 >= k / 2
的时候,len2 < k / 2
,即len2 >= k / 2
恒成立。
C++ 代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(),m = nums2.size(),sum = n + m;
if(sum % 2 == 0)
{
int left = getKthSmallest(nums1,0,nums2,0,sum / 2);
int right = getKthSmallest(nums1,0,nums2,0,sum / 2 + 1);
return (left + right) / 2.0;
}else
return getKthSmallest(nums1,0,nums2,0,sum / 2 + 1);
}
int getKthSmallest(vector<int> &nums1,int i,vector<int> &nums2,int j,int k)
{
if(nums1.size() - i > nums2.size() - j) return getKthSmallest(nums2,j,nums1,i,k);
if(i == nums1.size()) return nums2[j + k - 1];
if(k == 1) return min(nums1[i],nums2[j]);
int si = min(i + k / 2,(int)nums1.size()),sj = j + k / 2;
if(nums1[si - 1] > nums2[sj - 1])
return getKthSmallest(nums1,i,nums2,j + k / 2,k - k / 2);
else
return getKthSmallest(nums1,si,nums2,j,k - (si - i));
}
};
写在最后:这道题是我力扣刷题以来遇到的最抽象的一道题。
两种方法的思路都解释得很清楚,赞一个hh
这道题目简直毒瘤,像是leetcode的劝退题。
出在第四题很险恶了,应该是谷歌的面试题
思路上倒不太难,主要是边界问题太多了,很繁琐。