两个有序数组中的中位数和Top K问题

先看# Voidsky的这篇算法说明
然后我用java实现了一下

 //寻找中位数
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        if (n > m) {
            //这里保证数组1为数目少的
            return findMedianSortedArrays(nums2, nums1);
        }
        int l1, l2, r1, r2, c1, c2;
        //数组1总数为2n+1 默认虚拟加了# 使用二分法
        c1 = n;
        while (true) {
            c2 = m + n - c1;
            l1 = c1 == 0 ? Integer.MIN_VALUE : nums1[(c1 - 1) / 2];
            r1 = (c1 == 2 * n) ? Integer.MAX_VALUE : nums1[c1 / 2];
            l2 = (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2 - 1) / 2];
            r2 = (c2 == 2 * m) ? Integer.MAX_VALUE : nums2[c2 / 2];
            if (l1 > r2) {
                c1--;
            } else if (l2 > r1) {
                c1++;
            } else {
                break;
            }
        }
        return (Integer.max(l1, l2) + Integer.min(r1, r2)) / 2.0;

    }

这里二分的实现和原作者有点不一样 ，但是原理一样，原作者二分法实现是这样的

 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        if(n > m)   //保证数组1一定最短
            return findMedianSortedArrays(nums2,nums1);
        int L1,L2,R1,R2,c1,c2,lo = 0, hi = 2*n;  //我们目前是虚拟加了'#'所以数组1是2*n+1长度
        while(lo <= hi)   //二分
        {
            c1 = (lo+hi)/2;  //c1是二分的结果
            c2 = m+n- c1;
            L1 = (c1 == 0)?INT_MIN:nums1[(c1-1)/2];   //map to original element
            R1 = (c1 == 2*n)?INT_MAX:nums1[c1/2];
            L2 = (c2 == 0)?INT_MIN:nums2[(c2-1)/2];
            R2 = (c2 == 2*m)?INT_MAX:nums2[c2/2];

            if(L1 > R2)
                hi = c1-1;
            else if(L2 > R1)
                lo = c1+1;
            else
                break;
        }
        return (max(L1,L2)+ min(R1,R2))/2.0;
    }

他是用了一个lo和hi其实就是数组开始和结束位置，然后通过二分来实现，可以对比我的方法看看