算法1 二分
参考文献
https://www.acwing.com/solution/LeetCode/content/4487/
C++ 代码
class Solution {
public:
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 left = 0,right = n,k = (n + m + 1) >> 1;
while(left <= right)
{
int i = (left + right) >> 1,j = k - i;
if(i < n && nums1[i] < nums2[j - 1] )
left = i + 1;
else if(i > 0 && nums1[i - 1] > nums2[j])
right = 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;
}
};
算法1延伸
参考文献
C++ 代码
class Solution {
public:
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 left = 0,right = n * 2;
int leftMax1, leftMax2, rightMin1, rightMin2;
int i, j;
while (left <= right) {
i = (left + right) >> 1;
j = m + n -i;
leftMax1 = (i == 0) ? INT_MIN :nums1[(i - 1) /2];
rightMin1 = (i == n * 2) ? INT_MAX : nums1[i /2];
leftMax2 = (j == 0) ? INT_MIN : nums2[(j - 1) / 2];
rightMin2 = (j == m * 2) ? INT_MAX :nums2[ j / 2];
if (leftMax2 > rightMin1)
left = i + 1;
else if (leftMax1 > rightMin2)
right = i - 1;
else
break;
}
return (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2.0;
}
};
算法2 分治法
参考文献
C++ 代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
if (len % 2 == 0) {
int left = getKthSmallest(nums1, 0, nums2, 0, len / 2);
int right = getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
return (left + right) / 2.0;
}
else
return getKthSmallest(nums1, 0, nums2, 0, len / 2 + 1);
}
int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
if (nums1.size() - start1 > nums2.size() - start2)
return getKthSmallest(nums2, start2, nums1, start1, k);
if (start1 == nums1.size())
return nums2[start2 + k -1];
if (k == 1)
return min(nums1[start1], nums2[start2]);
//缩小范围
int s1 = start1 + min(k / 2, int(nums1.size() - start1));
int s2 = start2 + min(k / 2, int(nums2.size() - start2));
if (nums1[s1 - 1] > nums2[s2 - 1])
return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
else
return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
}
};
算法2 分治法延伸
参考文献
C++ 代码
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len1 = nums1.size(), len2 = nums2.size(), len = len1 + len2;
int left = (len + 1) / 2;
int right = (len + 2) /2;
return (getKthSmallest(nums1, 0, nums2, 0, left) + getKthSmallest(nums1, 0, nums2, 0, right)) / 2.0;
}
int getKthSmallest(vector<int> &nums1, int start1, vector<int> &nums2, int start2, int k) {
if (nums1.size() - start1 > nums2.size() - start2)
return getKthSmallest(nums2, start2, nums1, start1, k);
if (start1 == nums1.size())
return nums2[start2 + k -1];
if (k == 1)
return min(nums1[start1], nums2[start2]);
//缩小范围
int s1 = start1 + min(k / 2, int(nums1.size() - start1));
int s2 = start2 + min(k / 2, int(nums2.size() - start2));
if (nums1[s1 - 1] > nums2[s2 - 1])
return getKthSmallest(nums1, start1, nums2, s2, k - (s2 - start2));
else
return getKthSmallest(nums1, s1, nums2, start2, k - (s1 - start1));
}
};