4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

题目大意:给两个升序数组,要求两个数组的中位数(处于中间大小的数,若总数为奇,则就是最中间的数,若为偶,就是最中间两数的平均值).
解题思路一:暴力法,两个数组按序插入,排成一个新数组,按值插入,复杂度O(m+n),然后直接求新数组的中位数.
代码一(暴力):

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int s1 = nums1.size();
        int s2 = nums2.size();
        int s3 = s1 + s2;
        vector<int> nums3(s3);
        double res = 0.0;
        for (int i = 0, j = 0, k = 0; i <= s1 && j <= s2 && k < s3; k++) {
            if (i == s1 && j < s2) {
                nums3[k] = nums2[j];
                j++;
                continue;
            } else if (j == s2 && i < s1) {
                nums3[k] = nums1[i];
                i++;
                continue;
            }
            if (nums1[i] <= nums2[j]) {
                nums3[k] = nums1[i];
                i++;
            } else if (nums1[i] > nums2[j]) {
                nums3[k] = nums2[j];
                j++;
            }
        }
        if (s3 % 2) {
            res = nums3[s3 / 2];
        } else {
            res = (double)(nums3[s3 / 2 - 1] + nums3[s3 / 2]) / 2;
        }
        return res;
    }
};

思路2：二分法。详细分析见
https://leetcode.com/problems/median-of-two-sorted-arrays/solution/
主要根据这个结论：

解释一下第一条，为何j=0，i=m和B[j-1]<=A[i]是等效的：
j=0，说明B的left长度为0，因此必然有B的left部分最大值<=A的right中最小值；
i=m，说明A的right长度为0，因此必然有A的left部分最大值<=B的right中最小值；
B[j-1]<=A[i]，这个不用解释了，即B的left中最大<=A的right中最小。
同理，i=0，j=n和A[i-1]<=B[j]也是这样分析。
这两个条件都必须满足。

此外为何j = (m+n+1)/2 - i?
因为分析中要将A，B划分成相等的两段
此时i+j=m-i+n-j， 即j=(m+n)/2-i

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

然而左右两段不一定相等（当m+n为奇数时）：i+j=m-i+n-j+1,即j=(m+n+1)/2-i
由于j是int类型，因此即使m+n是偶数，+1再除以2依然是原来的结果，就可以将m+n的奇数和偶数两种情况统一起来：
j = (m+n+1)/2 - i

代码2（二分）：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
        int m = A.size();
        int n = B.size();
        //有一个数组为空，直接求另一个的中位数
        if (m == 0) return n%2 ? B[n/2] : (B[n/2-1] + B[n/2]) / 2.0;
        if (n == 0) return m%2 ? A[m/2] : (A[m/2-1] + A[m/2]) / 2.0;
        if (m > n) {  //保证m<=n
            vector<int> temp = A, A = B, B = temp;
            int tmp = m, m = n, n = tmp;
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j > 0 && i < m && B[j-1] > A[i]) {
                iMin++;
            } else if (i > 0 && j < n && A[i-1] > B[j]) {
                iMax--;
            } else {
                int leftMax = 0;
                if (i == 0) leftMax = B[j-1];
                else if (j == 0) leftMax = A[i-1];
                else leftMax = max(A[i-1], B[j-1]);
                if ((m + n) % 2 == 1) return leftMax;

                int rightMin = 0;
                if (i == m) rightMin = B[j];
                else if (j == n) rightMin = A[i];
                else rightMin = min(A[i], B[j]);

                return (leftMax + rightMin) / 2.0;
            }
        }
    }
};