给定两个有序数组arr1 和 arr2 ，再给定一个int K，返回所有的数中第K小的数

要求长度如果分别为 N M，时间复杂度O（log(min{M,N}),额外空间复杂度O（1）

 

解决此题的方法跟之前的求两个数组求中位数的情况，如出一辙~ 非常给力！

 此题目需要分情况讨论： 

    假设长度较短的数组长度 lenS   较长的lenL

    情况1、 K<1  或者 K>lenS+lenL    k值无效

    情况2、 k<=lenS  分别在两数组选择第前 k个数， 然后取其中位数

    情况3、 k>lenL  

package TT;public class Test13 {  public static int getUpMedian(int[] a1, int s1, int e1,int[] a2, int s2, int e2){         int mid1 = 0;         int mid2 =0;         int offset = 0;         while(s1
     
      a2[mid2]) {                 e1 = mid1;                 s2 = mid2+offset;                    }else if(a1[mid1]
      
       arr1.length+arr2.length){                    throw new RuntimeException("too long");                }      int[] longs = arr1.length >=arr2.length ? arr1 :arr2;      int[] shorts = arr1.length 
       
        l){          if(shorts[kth-l-1]>=longs[l-1]){              return shorts[kth-l-1];          }          if(longs[kth-s-1]>=shorts[s-1]){              return longs[kth-s-1];          }          return getUpMedian(shorts, kth-l, s-1, longs, kth-s, l-1);                }            if (longs[kth-s-1]>=shorts[s-1]) {           return longs[kth -s -1];    }      return getUpMedian(shorts, 0, s-1, longs, kth-s, kth-1);        }        public static void main(String[] args ){            int[] a1 = new int[4];      int[] a2 = new int[4];             a1[0]=0;  a1[1]=1;  a1[2]=2; a1[3]=3;      a2[0]=4;  a2[1]=5;  a2[2]=5; a2[3]=6;            int kth=4;            int c = findKthNum( a1, a2, kth);      System.out.println(c);                          }          }
       
      
     

结果：