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

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

程序员文章站 2022-04-25 14:34:34
...

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

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

    }
}

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