问题描述
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)).
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
问题分析
这道题之前做了没有记录下来，导致现在又忘了。。。
现在觉得，此题关键在于将寻找中位数这个问题转换为寻找第K大的数。
update 5.3
今天看到一个新的思路。
找median其实就是将nums1, nums2各分割为左右两部分，使得两个序列的左部分合并后与右部分合并后长度相等，且左部分的最大值不大于右部分的最小值。
设nums1长度比nums2小，那么我们用二分的方法查找nums1的分割点，对于每个分割点，我们可以找到nums2中与之相对应的分割点（因为两个左部分个数之和是所有元素个数的一半）。
实现起来的难度主要在于边界条件。
AC代码1
class Solution {
public:
double findK(vector<int>& nums1, vector<int>& nums2, int p1, int p2, int len1, int len2, int k){
if (p1 == len1)
return nums2[p2+k-1];
if (p2 == len2)
return nums1[p1+k-1];
if (k == 1){
return min(nums1[p1], nums2[p2]);
}
bool flag1 = (len1-p1) >= k/2;
bool flag2 = (len2-p2) >= k/2;
if (flag1 && flag2){
if (nums1[p1+k/2-1] > nums2[p2+k/2-1])
return findK(nums1, nums2, p1, p2+k/2, len1, len2, k-k/2);
else if (nums1[p1+k/2-1] < nums2[p2+k/2-1])
return findK(nums1, nums2, p1+k/2, p2, len1, len2, k-k/2);
else if (k % 2 == 0)
return nums2[p2+k/2-1];
else
return findK(nums1, nums2, p1+k/2, p2+k/2, len1, len2, 1);
}
else if (flag1){
return findK(nums1, nums2, p1+k/2, p2, len1, len2, k-k/2);
}
else
return findK(nums1, nums2, p1, p2+k/2, len1, len2, k-k/2);
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size();
int len2 = nums2.size();
int k = (len1 + len2) / 2;
if ((len1 + len2) % 2 == 0){
double a = findK(nums1, nums2, 0, 0, len1, len2, k);
double b = findK(nums1, nums2, 0, 0, len1, len2, k+1);
return (a + b)/2;
}
else
return findK(nums1, nums2, 0, 0, len1, len2, k+1);
}
};
Runtime: 29 ms, which beats 99.11% of cpp submissions.
AC代码2
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
if (n > m)
return findMedianSortedArrays(nums2, nums1);
if (n == 0){
if (m % 2 == 0)
return (nums2[m/2] + nums2[m/2 - 1])/2.0;
else
return nums2[m/2];
}
int mini = 0;
int maxi = n;
int i, j;
while (mini <= maxi){
i = (mini + maxi)/2;
j = (m + n)/2 - i;
// cout << i << ' ' << j << endl;
if ((i >= n || j-1 < 0 || nums1[i] >= nums2[j-1]) && (i-1 < 0 || j >= m || nums1[i-1] <= nums2[j])){
break;
}
else if (i >= m || j < 0 || nums1[i-1] > nums2[j])
maxi = i-1;
else
mini = i+1;
// cout << "min-max:" << mini << ' ' << maxi << endl;
}
// cout << i << ' ' << j << endl;
double rst = 0;
if ((m+n) % 2 == 0){
if (i >= n){
if (j <= 0)
return (nums1[n-1] + nums2[0])/2.0;
else{
if(nums1[n-1] > nums2[j-1])
return (nums2[j] + nums1[n-1])/2.0;
else
return (nums2[j] + nums2[j-1])/2.0;
}
}
else if(i <= 0){
if (j >= m)
return (nums1[0] + nums2[m-1])/2.0;
else {
if(nums1[0] < nums2[j])
return (nums2[j-1] + nums1[0])/2.0;
else
return (nums2[j] + nums2[j-1])/2.0;
}
}
else{
if (nums1[i-1] > nums2[j-1])
rst += nums1[i-1];
else
rst += nums2[j-1];
if (nums1[i] < nums2[j])
rst += nums1[i];
else
rst += nums2[j];
return rst/2.0;
}
}
else{
if (i >= n){
if (j <= 0)
return nums2[0];
else
return nums2[j];
}
else if(i <= 0)
if (j >= m)
return nums2[m-1];
else
return nums2[j] < nums1[0] ? nums2[j] : nums1[0];
else{
if (nums1[i] > nums2[j])
return nums2[j];
else
return nums1[i];
}
}
}
};
讲真，写得相当丑了……
Runtime: 32 ms, which beats 95.90 % of cpp submissions.
