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

野性酷女 2022-05-26 01:06 188阅读 0赞

![这里写图片描述][70]

//在两个排序数组中找到第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;
             }
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220526/da01cf84691244749f6ab88795225a98.png
[70 1]: /images/20220526/e6196c8edb9f4495ae1fb1acd4a0f939.png