Median of Two Sorted Arrays

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

s1: sort然后直接找到median O(m+n) 实际上不用sort整个array，到index>(m+n)/2就可停止。

class Solution {
public: 
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums = sortTwoArray(nums1, nums2);
        int size = nums.size();
        double result;
        int index = size/2;
        if(size%2 == 1) result = nums[index];
        else result = (nums[index] + nums[index-1])/2.0;
        return result;
    }
    vector<int> sortTwoArray(vector<int>& nums1, vector<int>& nums2){
        int size = nums1.size() + nums2.size();
        vector<int> nums(size);
        int i = 0, j = 0, idx =0;
        while(i < nums1.size() && j < nums2.size()){
            if(nums1[i] <= nums2[j]) nums[idx++] = nums1[i++];
            else nums[idx++] = nums2[j++];
        }
        while(i < nums1.size()) {nums[idx++] = nums1[i++];}
        while(j < nums2.size()) {nums[idx++] = nums2[j++];}
        return nums;
    }
};

S2:devide & conquer 二分法 O(log(m+n))

更通用的解法：找到两个数组最小的第k个数。对于两个数组nums1,nums2, 如果nums1[k/2]小于 num2[k/2] 那么k一定不在nums1[0]到nums1[k/2]之间，这里排除了k/2个值，反之亦然。

//代码有问题
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int size = nums1.size() + nums2.size();
        double value1 = findKthNum(nums1, nums1.size(), 0, nums2, nums2.size(), 0, size/2+1);
        if(size & 0x1 == 0){
            int value2 = findKthNum(nums1, nums1.size(), 0, nums2, nums2.size(), 0, size/2);
            return (value1+value2)/2.0;
        } 
        else return value1;
    }
    //find the kth smallest value
    int findKthNum(vector<int>& nums1, int size1, int start1, vector<int>& nums2, int size2, int start2, int k){
        if(size1 == 0) return nums2[k-1];
        if(size2 == 0) return nums1[k-1];
        if(k == 1) return min(nums1[start1], nums2[start2]);
        if(size2 > size1) return findKthNum(nums2, size2, start2, nums1, size1, start1, k);
        //注意k/2比size2大的coner case
        int pivot2 = min(k/2, size2);
        int pivot1 = k-pivot1;
        if(nums1[start1+pivot1-1] == nums2[start2+pivot2-1]) return nums1[start1+pivot1-1];
        if(nums1[start1+pivot1-1] > nums2[start2+pivot2-1]) 
          return findKthNum(nums1, size1, start1, nums2, size1-pivot2, start2+pivot2, k-pivot2);
        else return findKthNum(nums1, size1-pivot1, start1+pivot1, nums2, size2, start2, k-pivot1);
    }
};