題目描述

自我嘗試

• 首先，就是兩個有序的數組進行遍歷，遍歷到一半即可。然后求出均值，下述是我的代碼。但這明顯是有問題的，具體錯誤的代碼如下。計算復雜度太高了，O（n），所以會超時，具體代碼如下
• 這說明一個問題，不能逐個遍歷，只要遍歷就一定有問題的，可以嘗試一下對折尋找。

   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {double numsLeft = 0,numsRight = 0;int len = nums1.size() + nums2.size(),index = 0;for(int i = 0, j = 0; i <= nums1.size() && j <= nums2.size();){if(nums1[i] < nums2[j])numsLeft = nums1[i ++] ;elsenumsLeft = nums2[j ++ ];if(index == len / 2 -1)  numsLeft = numsLeft;if(index == len / 2) numsRight = numsLeft;index ++;}if(len % 2 == 2)return (numsLeft + numsRight )/ 2;elsereturn numsRight;}

正常做法

• 這里僅僅講解二分法，只需要注意這里的k是在剩下的元素中，尋找第k小的數字即可

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int tot = nums1.size() + nums2.size();if(tot % 2 == 0){int left =  find(nums1,0,nums2,0,tot / 2);int right = find(nums1,0,nums2,0,tot / 2 + 1);return (left + right) / 2.0}else{return find(nums1,0,nums2,0,tot / 2 + 1);}
}int find(vector<int> nums1,int i,vector<int> nums2,int j,int k){/** k表示需要查找的第k個小數字，第一個數字，就表示兩個數組在可審查的范圍內，都要找第一個元素，所以僅僅比較最小值即可*/// 確保第一個vector的長度是最短的if(nums1.size() - i > nums2.size() - j) return find(nums2,j,nums1,i,k);// 已經排除了第k-1個元素，剩下的就是第k個元素了，所以僅僅需要比較當前兩個數組的最小的元素即可if (k == 1){if(nums1.size() == i)   return nums2[j];else return min(nums1[i],nums2[j]);}// 第一個數組已經完全檢查過了，完全都被排除了，所以，相當于直接在第二個數組中找第k個值if (nums1.size() == i) return nums2[j + k - 1];// 更新移動數組的下標，進行第二次迭代，這里是將元素進行第二次縮減，然后在進行查找。// si和sj是更新之后的新的數組的下標int si = min((int)nums1.size(),i + k / 2) ,sj = j + k - k / 2;if(nums1[si - 1] > nums2[sj - 1])return find(nums1,i,nums2,sj,k - (sj - j));elsereturn find(nums1,si,nums2,j,k-(si - i));
}

分析總結

• 還是適合中午或者下午做算法題，不然太難受了，一個上午都是暈乎乎的。