微软面试模拟题 Leetcode 4 两个排序数组找到第k小的数

这道题目比较难，首先与面试管沟通整体思路：

先取第一个数组的第k/2个数，和第二个数组的第k-k/2个数，如果这两个数相等，那么这个数就是第k小的数。

如果第一个数组的第k/2个数小于第二个数组的第k-k/2个数，那么答案一定不可能在第一个数组的start1到start1+k/2-1, 以及第二个数组的第k-k/2+1到end2，同时这个数就一定能砍掉na。

可以用反证法来证明，假设在第一个数组第k/2个数之前，那么相加一定超过k。如果在第二个数组的k-k/2之后，也会矛盾。

同理反过来也一样。

因此每一个可以将数组砍掉一半，时间复杂度log(n+m)

核心算法逻辑如下：

k/2有可能大于n1，第一个数组的长度，所以要做一个特殊处理。

        // na+nb = k, 且
        int na = min(k/2, n1);
        int nb = k - na;

        int v1 = nums1[start1+na-1];
        int v2 = nums2[start2+nb-1];
        if(v1==v2) return v1;
        // 那么答案只能在start+na到end，以及start2到start2+nb-1, k-na
        else if(v1<v2) return findKthSortedArrays(nums1,start1+na, end1, nums2, start2, start2+nb-1,k-na);
        else return findKthSortedArrays(nums1,start1,start1+na-1,nums2,start2+nb,end2, k-nb);

同时，这道题目还有一些边界条件，比如在处理的过程中，我们总是让第一个数组的长度小于第二个数组。

如果第一个数组的长度已经为0，就返回第二个数组中的第k个。

如果k=1，就返回两个数组中第一个元素。

    int findKthSortedArrays(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k){
        int n1 = end1 - start1 + 1;
        int n2 = end2 - start2 + 1;
        // 始终让第一个数组长度小于第二个数组长度
        if(n1>n2) return findKthSortedArrays(nums2,start2,end2,nums1,start1,end1,k);
        // n1=0的边界
        if(n1==0) return nums2[start2+k-1];
        // k=1的边界
        if(k==1) return min(nums1[start1],nums2[start2]);
        
        // na+nb = k, 且
        int na = min(k/2, n1);
        int nb = k - na;

        int v1 = nums1[start1+na-1];
        int v2 = nums2[start2+nb-1];
        if(v1==v2) return v1;
        // 那么答案只能在start+na到end，以及start2到start2+nb-1, k-na
        else if(v1<v2) return findKthSortedArrays(nums1,start1+na, end1, nums2, start2, start2+nb-1,k-na);
        else return findKthSortedArrays(nums1,start1,start1+na-1,nums2,start2+nb,end2, k-nb);
    }