4. 两个排序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为O(log (m+n)) 。
你可以假设 nums1 和 nums2 不同时为空。

示例1：
nums1=[1,3]
nums2=[2]
中位数是 2.0

示例2：
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5

思想主要参考官方

c++ code:

#include<iostream>
#include<algorithm>
#include<vector>
#include<sstream>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if (m == 0 && n == 0){ return -1; }
        if (m > n){//ensure j non negetive
            vector<int> temp = nums1; nums1 = nums2; nums2 = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax){
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i<iMax&&nums2[j - 1]>nums1[i])
            {
                iMin =i  + 1;
            }
            else if (i > iMin&&nums1[i - 1] > nums2[j])
            {
                iMax = i - 1;
            }
            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 ((m + n) % 2 == 1) return maxLeft;

                int minRight = 0;
                if (i == m){ minRight = nums2[j]; }
                else if (j == n){ minRight = nums1[i]; }
                else
                {
                    minRight = min(nums1[i], nums2[j]);
                }
                return (maxLeft+minRight)/2.0;

            }

        }
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<int> stringToIntegerVector(string input) {
    vector<int> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';
    while (getline(ss, item, delim)) {
        output.push_back(stoi(item));
    }
    return output;
}

int main() {
    string line;
    while (getline(cin, line)) {
        vector<int> nums1 = stringToIntegerVector(line);
        getline(cin, line);
        vector<int> nums2 = stringToIntegerVector(line);

        double ret = Solution().findMedianSortedArrays(nums1, nums2);

        string out = to_string(ret);
        cout << out << endl;
    }
    return 0;
}