4. Median of Two Sorted Arrays

Description

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)).

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

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

Solution

• 遍历计数法
  双指针遍历计数，注意m+n为奇偶的区别，时间复杂度O(m+n)，不满足题目要求，但也能AC

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    int i = 0, j = 0, median1 = 0, median2 = 0;
    int countNum = 0;
    while (i < m || j < n) {
        int A = (i<m?nums1[i]:INT_MAX);
        int B = (j<n?nums2[j]:INT_MAX);
        int smaller = (A<B?A:B);
        if (A < B) {
            i++;
        } else {
            j++;
        }
        countNum++;
        if (countNum == (m + n)/2) {
            median1 = smaller;
        } else if (countNum == (m + n)/2 + 1) {
            median2 = smaller;
            break;
        }
    }
    return (m + n)%2 == 0 ? (median1 + median2)/2.0 : median2;
}

• 二分法
  题目要求时间复杂度O(log(m+n))，考虑到数组有序，很自然需要借助二分法