Median of Two Sorted Arrays

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

函数$kth$表示归并两个数组时得到的第$k$个元素，函数的计算过程为，每次从$A$或$B$数组的其中一个数组中，找出$p$个元素，这$p$个元素不大于归并得到的第$k$个元素，接着把这$p$个元素排除掉，继续在$A$和$B$数组的剩余部分找归并$A$和$B$数组剩余部分后得到的第$k-p$个元素。 特殊地，当$k=1$或有一个数组为空时可以直接得到答案。 每次找到一个$p\in [1,\lfloor \frac{k}{2}\rfloor ]$，假设$A[0:p]$和$B[0:p]$都在归并的结果内，比较$A_p$和$B_p$，如果$A_p<B_p$则说明$A$中前$p$个元素都不大于归并后的第$k$个元素，否则说明$B$中前$p$个元素都不大于归并后的第$k$个元素。

当$p$取$\lfloor \frac{k}{2}\rfloor$时时间复杂度为$O(log(k))=O(log(n+m))$。

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);
    }
};