欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

在两个升序数组中找到第k小的数据

程序员文章站 2022-03-13 12:33:35
...
public static void main(String[] args) {
        int[] a=new int[]{1,2,3,4,5,6,11,12,13,14,15,21,22};
        int[] b=new int[]{7,8,9,10,16,17,18,19,20};
        System.out.println(kth_data(a, b, a.length, b.length, 17));


    }

    /**
     * 保证数组a为长度较小的数组,这样在算法实现时,只需考虑a的下标是否出界,简化问题
     */
    public static int kth_data(int[] a,int[] b,int al,int bl,int k){
        if(al<=bl){
            return kth_data(a, b, al-1, bl-1, (al-1)/2,k<=al-1?k-1:al-1,k);
        }else{
            return kth_data(b, a, bl-1, al-1, (bl-1)/2,k<=bl-1?k-1:bl-1,k);
        }

    }
    /**
     * 用pa和pb分别标记数组a和b的当前比较元素
     * pa+pb=k-1  该条件满足在pa之前有pa个元素,在pb之前有pb个元素
     * 当a[pa]==b[pb]时,a[pa]和b[pb]同时为第k个元素;
     * 当a[pa]<b[pb]时,1.如果此时pb==0,则a[pa]是第k个元素;
     *                2.如果a[pa]>=b[pb-1],则a[pa]是第k个元素;
     *                3.如果a[pa]<b[pb-1]且pa==a.length-1,则b[pb-1]是第k个元素;
     *                4.除以上三种情况外,pa右移,pb左移,移动长度delt
     * 当a[pa]>b[pb]时,1.如果此时pa==0,则b[pb]是第k个元素;
     *                2.如果b[pb]>=a[pa-1],则b[pb]是第k个元素;
     *                3.如果b[pb]<a[pa-1]且pb==b.length-1,则a[pa-1]是第k个元素;
     *                4.除以上三种情况外,pa左移,pb右移,移动长度delt
     * 继续递归。 (以上解释的逻辑顺序和代码顺序一致)
     */
    public static int kth_data(int[] a,int[] b,int al,int bl,int delt,int pa,int k){
        int pb=k-1-pa;
        if(a[pa]==b[pb]){
            return a[pa];
        }else if(a[pa]<b[pb]){
            if(pb==0||a[pa]>=b[pb-1]){
                return a[pa];
            }
            if(pa==al&&a[pa]<b[pb-1]){
                return b[pb-1];
            }
            pa+=delt;
        }else{
            if(pa==0||b[pb]>=a[pa-1]){
                return b[pb];
            }
            if(pb==bl&&b[pb]<a[pa-1]){
                return a[pa-1];
            }
            pa-=delt;
            pa=pa<0?0:pa;
        }
        return kth_data(a, b, al, bl, delt/2, pa, k);

    }