一直对二分法比较讨厌，今天做到了leetcoede第四题被难到了，做了好久才AC，这里写个博客来记录一下。
首先二分法的关键是找到上界和下界。同时也要注意边界条件。先来看看普通的暴力方法
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int temp = (nums1.size() + nums2.size()) / 2,count1 = 0,i = 0,j = 0,current,pre;
while(i < nums1.size() && j < nums2.size() && count1 <= temp)
{
pre = current;
if(nums1[i] > nums2[j])
current = nums2[j++];
else
current = nums1[i++];
++count1;
}
if(count1 <= temp)
{
if(i < nums1.size())
while(count1 <= temp)
{
pre = current;
current = nums1[i++];
++count1;
}
else
while(count1 <= temp)
{
pre = current;
current = nums2[j++];
++count1;
}
}
if((nums1.size() + nums2.size()) % 2)
return current;
//cout << current << " " << pre <<endl;
double ans = (current + pre) / 2.0;
return ans;
}
};
这种方法的时间复杂度为O(m+n),
第二种方法我们可以把这题看成寻找第k大的值，这样我们可以递归的去做，每次查找k / 2，直到k等于1，同时要注意边界值的处理
class Solution {
public:
int getKth(vector<int> nums1, int start1, int end1, vector<int> nums2, int start2, int end2, int k) {
int len1 = end1 - start1 + 1;
int len2 = end2 - start2 + 1;
if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
if (len1 == 0) return nums2[start2 + k - 1];
if (k == 1) return min(nums1[start1], nums2[start2]);
int i = start1 + min(len1, k / 2) - 1;
int j = start2 + min(len2, k / 2) - 1;
if (nums1[i] > nums2[j]) {
return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
}
else {
return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
}
}
double findMedianSortedArrays(vector<int> nums1, vector<int> nums2) {
int n = nums1.size();
int m = nums2.size();
int left = (n + m + 1) / 2;
int right = (n + m + 2) / 2;
return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
}
};
第三种方法我们可以利用中位数的定义，将两个数组划分为左右两个部分，nums1左半部分加nums2左半部分等于nums1右半部分加nums2的右半部分，如果总长度为偶数，那么nums1左半部分加nums2左半部分等于nums1右半部分加nums2的右半部分加1。并且max(nums1[i],nums2[j]) <= max(nums1[i + 1],nums2[j + 1])，接下来我们只要二分查找找i，并且要注意边界情况
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size(),sum = m + n;
if(!nums1.size())
return sum % 2 ? nums2[sum / 2] : (nums2[sum /2] + nums2[sum / 2 - 1]) / 2.0;
if(!nums2.size())
return sum % 2 ? nums1[sum / 2] : (nums1[sum /2] + nums1[sum / 2 - 1]) / 2.0;
if(m > n)
return findMedianSortedArrays(nums2,nums1);
int l = 0,r = m - 1;
while(l < r)
{
int mid = (l + r) / 2;
int j = (sum + 1) / 2 - mid - 2;
int min1 = max(nums1[mid],nums2[j]),max1 = min(nums1[mid + 1],nums2[j + 1]);
if(min1 <= max1)
return sum % 2 ? min1 : (min1 + max1) / 2.0;
else if(nums1[mid] > nums2[j])
r = mid - 1;
else
l = mid + 1;
}
int j = (sum + 1) / 2 - l - 2;
int min1,max1;
if(j < 0)
min1 = nums1[l];
else
min1 = max(nums1[l],nums2[j]);
if(l == nums1.size() - 1)
max1 = nums2[j + 1];
else
max1 = min(nums1[l + 1],nums2[j + 1]);
if(min1 <= max1)
return sum % 2 ? min1 : (min1 + max1) / 2.0;
j++;
if(j < nums2.size() - 1)
max1 = min(nums1[l],nums2[j + 1]);
else
max1 = nums1[l];
min1 = nums2[j];
return sum % 2 ? min1 : (min1 + max1) / 2.0;
}
};
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/20743.html