leetcode-寻找两个正序数组的第K大的数

两个正序数组（从小到大）， 找到两个数组的所有元素里的第K大的数。

思路

对两个有序数组同时使用二分法，由于是K个，将问题转化为K为了数组的中位数，然后利用中位数的特性，若当前数不满足条件，就舍弃掉之前的所有的元素

代码

class Solution {
public:
    int FindkthNum(vector<int> nums1,int index1, vector<int> nums2, int index2, int K) {
        if (index1 == nums1.size()) return nums2[index2 + K - 1];
        if (index2 == nums2.size()) return nums1[index1 + K - 1];
        if (K == 1) return min(nums1[index1], nums2[index2]);

        //二分的中间值
        //判断此时是否超出边界
        int mid1 = ((index1 + K/2 - 1) < nums1.size()) ? nums1[index1 + K/2 - 1] : INT_MAX;
        int mid2 = ((index2 + K/2 - 1) < nums2.size()) ? nums2[index2 + K/2 - 1] : INT_MAX;

        //对比，然后舍弃掉中位数之前的数
        if (mid1 < mid2)
            return FindkthNum(nums1, index1+K/2, nums2, index2, K - K/2);
        else
            return FindkthNum(nums1, index1, nums2, index2 + K/2, K - K/2);
    }
};

复杂度

时间：O（log(m+n)）, 空间O(log(m+n))