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);
}
在两个升序数组中找到第k小的数据
程序员文章站
2022-03-13 12:33:35
...
上一篇: 碰撞检测