两个有序数组，找第k小的数//未完

1、题目描述：a,b两个有序数组，找出第k小的数，logk，二分查找，1个小于怎么办？

2、思路：

时间复杂度为O(log(m+n))，自然想到可能会用二分法

假设A 和B 的元素个数都大于k/2，我们将A 的第k/2 个元素（即A[k/2-1]）和B 的第k/2个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k 为偶数，所得到的结论对于k 是奇数也是成立的）：
• A[k/2-1] == B[k/2-1]
• A[k/2-1] > B[k/2-1]
• A[k/2-1] < B[k/2-1]

如果A[k/2-1] < B[k/2-1]，意味着A[0] 到A[k/2-1] 的肯定在A 与B 的所有元素的前k个元素的范围内，也就是说，A的前（k/2-1）个元素中不可能存在大于A与B所有元素的第k小元素。

因此，我们可以放心的删除A 数组的这k/2 个元素。同理，当A[k/2-1] > B[k/2-1] 时，可
以删除B 数组的k/2 个元素。
当A[k/2-1] == B[k/2-1] 时，说明找到了第k 大的元素，直接返回A[k/2-1] 或B[k/2-1]
即可。

因此，我们可以写一个递归函数。那么函数什么时候应该终止呢？
• 当k=1 是，返回min(A[0], B[0])；
• 当A[k/2-1] == B[k/2-1] 时，返回A[k/2-1] 或B[k/2-1]

但是可能出现如果A中有3个元素，B中有12个元素，我们要找A与B所有元素的第8小元素，这时m < k/2
当出现这种情况时，我们可以取A中的所有元素，取B中的前k-m个元素
也可以按比例来取，比如取A中的前(m/(m+n))*k个元素，取B中前（k-(m/(m+n))*k）个元素

3、代码：

public class Solution {
    public static void main(String[] args) {
        //定义两个有序数组a,b
        int[] a = new int[]{1,9,10,18};
        int[] b = new int[]{7,10};

        //查找两个数组的第k小元素
        int k = 5;
        System.out.println(Search(a,0,a.length-1,b,0,b.length-1,k));

    }

    public static int Search(int[] a,int startA,int endA,int[] b,int startB,int endB,int k){
        if(k == 1){
            if(a[startA] <= b[startB]){
                return a[startA];
            }else{
                return b[startB];
            }
        }

        //如果startA>endA,则说明A中的元素已经排除完，只剩下B中元素，此时只要取B中前k个元素就好
        if(startA > endA){
            return b[startB + k - 1];
        }
        //同上
        if(startB > endB){
            return a[startA + k -1];
        }

        int al = endA - startA + 1;
        int bl = endB - startB + 1;

        //如果a中元素个数大于b中元素个数，此时应该将a与b的位置交换，将元素少的数组放在前面，这是为了57行代码的判断
        if(al > bl){
            return Search(b,startB,endB,a,startA,endB,k);
        }

        int ms = 0;
        int ns = 0;

        //如果a中元素个数<k/2,此时应该取a中的所有元素,如果不做49的行的处理的话，可能会造成数组溢出
        if((endA - startA + 1) < k/2){
            ms = endA - startA + 1;
        }else{
            ms = k/2;
        }

        ns = k - ms ;

        int m = ms-1 + startA;
        int n = ns-1+ startB;

        if(a[m] == b[n]){
            return a[m];
        }else if(a[m] > b[n]){
            return Search(a,startA,m,b,n+1,endB,k-ns);
        }else{
            return Search(a,m+1,endA,b,startB,n,k-ms);
        }

    }

}

参考博客：https://blog.csdn.net/peach90/article/details/45599843

两个有序数组，找第k小的数//未完

推荐阅读