给定两个有序数组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<e1){
mid1 = (s1+e1) /2;
mid2 = (s2+e2) /2;
offset = ((e1-s1+1)&1)^1;
if (a1[mid1]>a2[mid2]) {
e1 = mid1;
s2 = mid2+offset;
}else if(a1[mid1]<a2[mid2]){
s1 = mid1 + offset;
e2= mid2;
}else {
return a1[mid1];
}
}
return Math.min(a1[s1], a2[s2]);
}
public static int findKthNum(int[] arr1, int[] arr2, int kth){
if(arr1==null || arr2==null){
throw new RuntimeException("are you ok?");
}
if(kth<1 || kth>arr1.length+arr2.length){
throw new RuntimeException("too long");
}
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(kth <= s){
return getUpMedian(shorts, 0, kth-1, longs, 0, kth-1);
}
if(kth>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);
}
}
结果：
