微軟面試題: 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 };