leetcode每日一题 leetcode4

这道题自己首先想到的就是利用归并排序的感觉，用两个指针分别扫描两个数组，查找中间元素

自己写的代码竟然超时了。。

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {bool whetherodd = true;bool iorj = true; //true表示最后一次移动为iint length = nums1.size() + nums2.size();int n = 0;if((length & 1 ) == 0 ) whetherodd = false;n = length / 2;int times = 0;int i = 0 , j = 0;while( times != n + 1 && i < nums1.size() && j < nums2.size() ){ //n + 1比较好追溯上一个移动的if( nums1[i] <= nums2[j]) i++;else{j ++; iorj = false;}times ++;}if(times == n + 1){if(whetherodd == true ){if(iorj == false )return nums2[j - 1];elsereturn nums1[i - 1];} else{if(iorj == false )return ((double)nums2[j - 1] + (double)nums2[j] ) / 2;elsereturn ((double)nums1[i - 1] + (double)nums1[i] ) / 2;}}else if(i == nums1.size()){while(times != n + 1 ){j ++;times ++;}if( whetherodd == true ) return nums2[ j - 1 ];else if( nums1.size() == nums2.size() )return ((double)nums2[j - 1] + (double)nums1[i-1] ) / 2;elsereturn ((double)nums2[j - 1] + (double)nums2[j] ) / 2; //这里如果其长度一样就出错了}else if( j == nums2.size()){while(times != n + 1 ){ i ++; times ++; }if( whetherodd == true ) return nums2[ i - 1 ];else if( nums1.size() == nums2.size() )return ((double)nums2[i - 1] + (double)nums1[j-1] ) / 2;elsereturn ((double)nums2[i - 1] + (double)nums2[i] ) / 2;}return 0.0;}
};

明后天复试，没有时间康了，先搬运一下bobo老师的答案 ,复试完来填坑

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {if(nums1.size() > nums2.size()) swap(nums1, nums2);int n = nums1.size(), m = nums2.size();if(n == 0) return m % 2 ? nums2[m / 2] : (nums2[m / 2 - 1] + nums2[m / 2]) / 2.0;int half = (n + m) / 2;int l = 0, r = n;while(l <= r){int mid = (l + r) / 2;int i1 = mid, i2 = half - i1;int leftMax = i1 == 0 ? nums2[i2 - 1] :i2 == 0 ? nums1[i1 - 1] : max(nums1[i1 - 1], nums2[i2 - 1]);int rightMin = i1 == n ? nums2[i2] :i2 == m ? nums1[i1] : min(nums1[i1], nums2[i2]);if(leftMax <= rightMin){if((n + m) % 2 == 1)return rightMin;else{int nums1Left = i1 == 0 ? INT_MIN :i1 == 1 ? nums1[i1 - 1] : max(nums1[i1 - 1], nums1[i1 - 2]);int nums1Right = i1 == n ? INT_MAX :i1 == n - 1 ? nums1[i1] : min(nums1[i1], nums1[i1 + 1]);int nums2Left = i2 == 0 ? INT_MIN :i2 == 1 ? nums2[i2 - 1] : max(nums2[i2 - 1], nums2[i2 - 2]);int nums2Right = i2 == m ? INT_MAX :i2 == m - 1 ? nums2[i2] : min(nums2[i2], nums2[i2 + 1]);return (max(nums1Left, nums2Left) + min(nums1Right, nums2Right)) / 2.0;}}else if(nums1[i1] == rightMin)l = mid + 1;elser = mid - 1;}assert(false);return -1;}
};