Median of Two Sorted Arrays

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

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();
        if (n % 2 == 1)
            return kth(nums1, 0, nums2, 0, n / 2 + 1);
        else
            return (kth(nums1, 0, nums2, 0, n / 2) + kth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
    }
    int kth(vector<int> &nums1, int n1, vector<int> &nums2, int n2, int k) {
        if (nums1.size() - n1 > nums2.size() - n2)
            return kth(nums2, n2, nums1, n1, k);
        if (nums1.size() - n1 == 0)
            return nums2[n2 + k - 1];
        if (k == 1)
            return min(nums1[n1], nums2[n2]);
        
        int p = min(k / 2, int(nums1.size() - n1));
        if (nums1[n1 + p - 1] < nums2[n2 + p - 1])
            return kth(nums1, n1 + p, nums2, n2, k - p);
        else
            return kth(nums1, n1, nums2, n2 + p, k - p);
    }
};

Median of Two Sorted Arrays

原文：https://www.cnblogs.com/ToRapture/p/12115060.html