微軟面試題: LeetCode 4. 尋找兩個正序數組的中位數 hard 出現次數:3
題目描述:
給定兩個大小為 m 和 n 的正序(從小到大)數組 nums1
和 nums2
。請你找出並返回這兩個正序數組的中位數。
進階:你能設計一個時間複雜度為 O(log (m+n))
的算法解決此問題嗎?
方法1:
總體思路: 同時遍歷 num1 和nums2 ,比較num1和nums2中當前遍歷到的兩個元素 nums1[i] 和 nums[j] 的大小。若nums1[i] 小則
i 前進一位,j 不動,反之,j 前進一位 ,i 不動,直到遍歷到中位數的下標 或者 其中一個數組遍歷結束 再繼續單獨遍歷另一個數組,
直到找到中位數。由於 中位數需要根據 元素個數是奇數和偶數兩種情況討論,此種算法實現上細節判斷較多,容易出錯,最終寫出的代碼
結構也比較凌亂。且 時間複雜度 O(m + n),空間複雜度O(1) 性能上也不符合題目的要求。
重點關注第二種 O(log (m+n))
的算法
1 #include <string> 2 #include <vector> 3 #include <cmath> 4 5 using namespace std; 6 class Solution { 7 public: 8 //O(m+n) 9 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 10 { 11 int m = nums1.size(); 12 int n = nums2.size(); 13 bool odd = true;//奇數 14 if( (m+n) % 2 == 0) odd = false;//偶數 15 int mid = (m+n)/2; 16 int k = 0; 17 int front = 0; 18 int i = 0,j = 0; 19 for(;i<m && j<n;) 20 { 21 if(k == mid) 22 { 23 if(odd) 24 { 25 return nums1[i]<nums2[j]?nums1[i]:nums2[j]/1.000000; 26 } 27 else 28 { 29 int tmp = nums1[i]<nums2[j]?nums1[i]:nums2[j]; 30 return (tmp+front)/2.000000; 31 } 32 } 33 else 34 { 35 if(nums1[i]<nums2[j]){ 36 front = nums1[i]; 37 i++; 38 } 39 else 40 { 41 front = nums2[j]; 42 j++; 43 } 44 k++; 45 } 46 } 47 // printf("k = %d mid = %d i = %d j = %d \n",k,mid,i,j); 48 if(k == 0) 49 { 50 if(j == n) 51 { 52 return odd?nums1[mid]/1.0:(nums1[mid]+nums1[mid-1])/2.0; 53 } 54 else if(i == m){ 55 return odd?nums2[mid]/1.0:(nums2[mid]+nums2[mid-1])/2.0; 56 } 57 else{ 58 return 0.000000; 59 } 60 } 61 if(odd) 62 { 63 int index ; 64 if(j == n ) //j 已經走完 i 未走完 65 { 66 index = i + (mid+1 - k)-1 ; 67 return index < m?nums1[index]/1.000000:0.000000; 68 // return nums1[index]; 69 } 70 else 71 { 72 index = j + (mid+1 - k)-1; 73 return index < n?nums2[index]/1.000000:0.000000; 74 // return nums2[index]; 75 } 76 } 77 else 78 { 79 if(j == n) 80 { 81 int idx = i + (mid+1 - k) -1; 82 if(idx <= 0 ) 83 { 84 return (nums2[n-1] + nums1[0])/2.000000; 85 } 86 else 87 { 88 int frt = max(nums1[idx-1],nums2[n-1]); 89 return (nums1[idx] + frt)/2.000000; 90 } 91 } 92 else 93 { 94 int idx = j + (mid+1 - k) -1; 95 if(idx <= 0 ) 96 { 97 return (nums1[m-1] + nums2[0])/2.000000; 98 } 99 else 100 { 101 int frt = max(nums2[idx-1],nums1[m-1]); 102 return (nums2[idx] + frt)/2.000000; 103 } 104 } 105 } 106 } 107 };
View Code
方法2:轉化為求第 k
小數的元素
分析:上面的解法中 同時遍歷兩個數組中的元素並比較大小,對小的元素,在該數組中前進,並統計前進的步數,前進到 (n + m)/2 步,就遍歷到
中位數。每次前進相當於去掉不可能是中位數的一個值,也就是一個個排除。由於數列是有序的,其實我們完全可以一半兒一半兒的排除。
具體思路可參考://leetcode.wang/leetCode-4-Median-of-Two-Sorted-Arrays.html
代碼如下:
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 4 { 5 int n = nums1.size(); 6 int m = nums2.size(); 7 int left = (n + m +1)/2; 8 int right = (n + m +2)/2; 9 //將n+m是奇數和偶數的情況合併,如果是奇數,會求兩次兩同的k,最終返回兩個正序數組的一個中位數 10 //如果是偶數,最終返回兩個正序數組的中間兩個中位數的平均值 11 return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5; 12 } 13 /* 14 使用二分法 15 求 nums1[start1,end1]和 nums2[start2:end2]的第k小元素 16 */ 17 double getKth(vector<int>& nums1, int start1,int end1,vector<int>& nums2,int start2,int end2,int k) 18 { 19 int len1 = end1 - start1 +1; 20 int len2 = end2 - start2 +1; 21 //始終將元素少的那個數組作為第一個參數,這樣就能保證如果有數組空了,一定是第一個參數的數組 22 if(len1 > len2){ 23 return getKth(nums2,start2,end2,nums1,start1,end1,k); 24 } 25 //遞歸出口1,nums1[start1,end1]空了,返回nums2[start2,end2]中的 第 k 個元素 26 if(len1 == 0) 27 { 28 return nums2[start2 + k - 1]; 29 } 30 //遞歸出口2,返回兩個數組的第 start 個元素中較小的一個 31 if(k == 1) 32 { 33 return min(nums1[start1+k-1],nums2[start2+k-1]); 34 } 35 //nums1[start1:end1] 中 第 k/2 個元素的下標,如果nums1[start1:end1] 長度小於 k/2,則取nums[start1:end1]最後一個元素下標 36 int i = start1 + min(k/2,len1) - 1; 37 //nums2[start2:end2] 中 第 k/2 個元素的下標,nums2[start2:end2] 長度一定不會小於 k/2 38 int j = start2 + k/2 - 1; 39 //int j = start2 + min(k/2,len2) - 1; 40 //遞歸地求 第 k、k/2、k/4、... 、1 個元素,直到遇到遞歸出口跳出 41 if(nums1[i] < nums2[j]) 42 { 43 return getKth(nums1,i+1,end1,nums2,start2,end2,k - (i - start1 +1)); 44 } 45 else 46 { 47 return getKth(nums1,start1,end1,nums2,j+1,end2,k - (j - start2 +1)); 48 } 49 } 50 };