在两个排序数组中找到第k小的数
程序员文章站
2022-04-25 14:34:34
...
//在两个排序数组中找到第k小的数
public class FindMinK{
//(1)寻找上中位数的算法
public static int getUpMedia(int[]arr1,int s1,int e1,int[]arr2,int s2,int e2){
int mid1=0;
int mid2=0;
int offset=0;
while(s1<e1){
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
offset=((e1-s1+1)&1)^1;
if(arr1[mid1]>arr2[mid2]){
e1=mid1;
s2=mid2+offset;
}else if(arr1[mid1]<arr2[mid2]){
s1=mid1+offset;
e2=mid2;
}else{
return arr1[mid1];
}
}
return Math.min(arr1[s1],arr2[s2]);
}
//(2)寻找篇排数组的第k小的数
public static int FindMinKNum(int[]arr1,int[]arr2,int k){
if(arr1==null||arr2==null){
throw new RuntimeException("Your arr is invalid!");
}
if(k<1||k>(arr1.length+arr2.length)){
throw new RuntimeException("K is invalid!");
}
int[]longs=arr1.length>=arr2.length?arr1:arr2; //较长的数组
int[]shorts=arr1.length<arr2.length?arr1:arr2; //较短的数组
int l=longs.length;
int s=shorts.length;
if(k<=s){
return getUpMedia(shorts,0,k-1,longs,0,k-1);
}
if(k>l){
if(shorts[k-l-1]>=longs[l-1]){
return shorts[k-l-1];
}
if(longs[k-s-1]>=shorts[s-1]){
return longs[k-s-1];
}
return getUpMedia(shorts,k-l,s-1,longs,k-s,l-1);
}
if(longs[k-s-1]>=shorts[s-1]){
return longs[k-s-1];
}
return getUpMedia(shorts,0,s-1,longs,k-s,k-1);
}
public static void main(String[]args){
//System.out.println("Hello");
int[]arr1={1,2,3,4,5};
int[]arr2={3,4,5};
int k=1;
while(k<=arr1.length+arr2.length)
{
System.out.println(FindMinKNum(arr1,arr2,k));
++k;
}
}
}
推荐阅读
-
#7 找出数组中第k小的数
-
Java算法(递归):两个不同长度的有序数组求第k小的元素(时间复杂度为:O(log(m1 + m2)))。
-
在未排序的数组中找到第 k 个最大的元素
-
#7 找出数组中第k小的数
-
基于Partition函数实现查找数组中第K小的数+第K大的数
-
冒泡排序_快速排序(划分)_1求数组中第k大的数_2求数组中出现次数超过一半的数_3求数组中最小的k个数
-
在两个排序数组中找到第k小的数
-
Java算法(递归):两个不同长度的有序数组求第k小的元素(时间复杂度为:O(log(m1 + m2)))。
-
在未排序的数组中找到第 k 个最大的元素
-
面试算法:lg(k)时间查找两个排序数组合并后第k小的元素