LeetCode | 4)Median of Two Sorted Arrays

題目

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

代碼原型

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

};
           

思路

• 中位數是有序清單中最中間的那個數，如果清單數有偶數個，則是中間兩個數的平均。
• 這道題可以在O(m + n)時間内通過周遊解出來，但題目要求用O(log(m+n))的時間複雜度，是以不得不考慮用折半查找的方法。
• 對于兩個已排序的數組找到它們的中位數，就是要找到A數組和B數組的分割線，使得

  A[i-1] < B[j]

  ，

  B[j-1] < A[i]

  ，而A[i - 1]本來就小于A[i]，B[j-1]本來就B[j]。這樣，分割線左邊的數從A[0]到A[i-1]和B[0]到B[j-1]都小于右邊，于是就找到了中位數。

  A[0] ... A[i - 1] | A[i] ... A[n - 1]
  B[0] ... B[j - 1] | B[j] ... B[m - 1]
             

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            nums1.swap(nums2);
        }
        int size1{nums1.size()}, size2{nums2.size()};
        int sizeall = size1 + size2;
        int mid = (sizeall - )/;
        int l{}, r{size1 - };
        while (l <= r){
        //确定l和r，使得nums1[r] < nums2[mid - r], nums1[l] > num2[mid - l]
            int m1 = (r + l)>>, m2 = mid - m1;
            if (nums1[m1] < nums2[m2]) {
                l = m1 + ;   
            }
            else {
                r = m1 - ;
            }
        }
        int a = max(r >=  ? nums1[r] : , mid - l >=  ? nums2[mid - l] : );
        //計算左邊數的最大值作為中值。
        if (sizeall&) //如果整個數組的大小為奇數，則a就是中值
            return a;
        else { //否則，還要計算右邊的最小值b，與a相加除以2得中值
            int b = min(l < size1 ? nums1[l] : INT_MAX, mid - r < size2 ? nums2[mid - r] : INT_MAX);
            return (a + b)/;
        }
    }
};
           

運作時間 35 ms