LeetCode problem 4. Median of Two Sorted Arrays

我不是女神ヾ 2022-06-01 01:25 151阅读 0赞

### 问题描述 ###

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

> 找中间数字。

--------------------

### 例子 ###

Example 1:  
nums1 = \[1, 3\]  
nums2 = \[2\]  
The median is 2.0

Example 2:  
nums1 = \[1, 2\]  
nums2 = \[3, 4\]  
The median is (2 + 3)/2 = 2.5

--------------------

### 思路 ###

1.  合并两个数组，然后找到中间值。这是最笨的方法。
2.  题目没有要求输出合并后的数组，所以没必要全部比较，可以记录比较的长度，只要达到中间长度就停止。
3.  进一步优化，不用辅助数组，试探性查找。

--------------------

### 代码 ###

/** 
        * 将两者不完全合并，即只要合并到len长度即可。
        * 用了一个辅助vector。 68ms
        */
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size(), len2=nums2.size();
            int len = (len1+len2)/2, f = (len1+len2)%2;
            vector<int> tem;
            double ans = 0;
            int i = 0, j= 0;
    
            while(i<len1&&j<len2&&i+j<len+1){
               if(nums1[i]>nums2[j]){
                  tem.push_back(nums2[j]);
                  j++;
               }else{
                  tem.push_back(nums1[i]);
                  i++;
               }
    
               cout<<i<<" "<<j<<endl;
            }
            while(i+j<len+1){
                if(i<len1){
                  tem.push_back(nums1[i]);
                  i++;
                }
                if(j<len2){
                   tem.push_back(nums2[j]);
                  j++;
                }
                cout<<i<<" "<<j<<endl;
            }
            cout<<i<<" "<<j<<" "<<len<<endl;
            if(f>0){
                ans = tem[len];
            }else{
                ans = double(tem[len-1]+tem[len])/2;
            }
    
            return ans;
    
        }

/**
        * 不用vector 思路一样  但用了更长的时间  90ms
        */
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size(), len2=nums2.size();
            int len = (len1+len2)/2, f = (len1+len2)%2;
            double ans = 0, tem = 0;
            int i = 0, j= 0;
    
            while(i<len1&&j<len2&&i+j<len+1){
               if(nums1[i]>nums2[j]){
                  if(i+j==len-1){
                      tem = nums2[j];
                  }
                  if(i+j==len){
                      ans = nums2[j];
                  }
                  j++;
               }else{
                  if(i+j==len-1){
                      tem = nums1[i];
                  }
                  if(i+j==len){
                      ans = nums1[i];
                  }
                  i++;
               }
    
               cout<<i<<" "<<j<<endl;
            }
            while(i+j<len+1){
                if(i<len1){
                  if(i+j==len-1){
                      tem = nums1[i];
                  }
                  if(i+j==len){
                      ans = nums1[i];
                  }
                  i++;
                }
                if(j<len2){
                  if(i+j==len-1){
                      tem = nums2[j];
                  }
                  if(i+j==len){
                      ans = nums2[j];
                  }
                  j++;
                }
                cout<<i<<" "<<j<<endl;
            }
            cout<<i<<" "<<j<<" "<<len<<endl;
            if(f>0){
                return ans;
            }else{
                return (ans+tem)/2;
            }
        }

/**
        *  例程进一步优化，55ms
        **/
         double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int len1 = nums1.size(), len2=nums2.size();
            if(len1>len2){
                vector<int> tem = nums1; nums1 = nums2; nums2=tem;
                int t = len1; len1 = len2; len2 = t;
            }
            int iMin = 0, iMax = len1, half = (len1+len2+1)/2;
            while(iMin <= iMax){
               int i = (iMin + iMax)/2;
               int j = half - i;
                if (i < iMax && nums2[j-1] > nums1[i]){
                    iMin = iMin + 1; // i is too small
                }
                else if (i > iMin && nums1[i-1] > nums2[j]) {
                    iMax = iMax - 1; // i is too big
                }
                else { // i is perfect
                    int maxLeft = 0;
                    if (i == 0) { maxLeft =nums2[j-1]; }
                    else if (j == 0) { maxLeft = nums1[i-1]; }
                    else { maxLeft = max(nums1[i-1], nums2[j-1]); }
                    if ( (len1 + len2) % 2 == 1 ) { return maxLeft; }
    
                    int minRight = 0;
                    if (i == len1) { minRight = nums2[j]; }
                    else if (j == len2) { minRight = nums1[i]; }
                    else { minRight = min(nums2[j], nums1[i]); }
    
                    return (maxLeft + minRight) / 2.0;
                }
            }
            return 0.0;
        }