题目描述
两个TopK的数组，求第K大的数。同时考虑各种类型的边界情况，要求实现时间复杂度log (k)
思路
方法是基于中位数的比较。为什么使用中位数而不是在两个数组中各取k/2大的数呢？
是因为只要数组的长度不为0，那么中位数总是存在的，而第K/2的数就不一定了，数组的长度很有可能小于k/2。通过这样的方法我们可以规避一大票边界问题。
我们按三种情况讨论：
2个数组的长度均为奇数
2个数组的长度均为偶数
2个数组的长度一奇一偶
（1）2个数组的长度均为奇数
我们设a数组的中位数下标为x，b数组的中位数下标为y，则如下图所示，a数组的长度为2x+1，b数组的长度为2y+1，总的元素的个数为2x+2y+2。
我们现在需要探讨的就是k是大于x+y+1，还是小于x+y+1的情况，也就是我们想找的第k大的数是在a、b数组归并后的数组中的前一半内，还是在后一半内。不失一般性，我们讨论当a[x] <= b[y]的情况，
a[x] <= b[y]存在两种：
k <= x + y + 1
当k <= x + y + 1，也即k属于归并数组的前一半时，从下图可以看出黄色区域明显不包含第k个数。原因很简单，因为b[y]大于等于蓝色部分的数，而蓝色部分的数目即为x+y+1，恰好为全体数的前一半的个数，也就是说黄色区域的数不可能属于归并后的前一半数组，可以排除在外，在剩余的两个数组中寻找第k大数。
当k > x + y + 1
当k > x + y + 1，也即k属于归并后数组的后一半，那么从下图可以看出黄色区域明显不包含第k个数。原因是黄色区域的数必然小于蓝色区域的数，而蓝色区域的数的数目之和即为x+y+1，恰好为归并后数组的和的一半，因此可以将黄色区域排除在外，注意在剩余的两个 数组中寻找第 k - x -1 大数。
当 a[x] > b[y]时，只是上述的情况反一下。
（2）2个数组的长度均为偶数
我们寻找a数组的上中位下标，记为x，b数组的下中位下标，记为y，如下图所示。这样错开中位数的目的是为了在将来做排除时能够保证像奇数情况下能将第k大数归类到前一半或者后一半的完美性质。
这样看来，a数组长度为2x + 2，b数组长度为2y，因此归并后的数组长度为2x + 2y + 2，与奇数情况一致。
不失一般性，我们讨论a[x] <= b[y]的情况。
a[x] <= b[y]存在两种：
k <= x + y + 1
当k <= x + y + 1，也即k属于归并数组的前一半时，如下图所示。显然黄色部分可以排除在外，因为黄色部分一定大于等于蓝色部分，而蓝色部分的长度之和为x+y+1，恰好为归并数组的一半。也就是说黄色部分必然位于归并数组的后一半，不可能包含第k个数。之后我们在排除了黄色区域的两个数组中寻找第k个数。
当k > x + y + 1
当k > x + y + 1，也即k属于归并数组的后一半时，如下图所示。显然黄色部分可以排除在外，因为黄色部分一定小于蓝色部分，而蓝色部分的长度之和为x+y+1，恰好为归并数组的一半。也就是说黄色部分必然位于归并数组的前一半，不可能包含第k个数。之后我们在排除了黄色区域的两个数组中寻找第k - x - 1个数。
当 a[x] > b[y]时，只是上述的情况反一下。
（3）2个数组的长度一奇一偶
若 k = 1，那么直接返回min(a[0], b[0])即可。
若 k > 1，不妨假设 a[0] < b[0]，那么a[0]必然是两个数组中最小的数，那么排除a[0]后我们可以在a、b两个数组中寻找第k-1个数，并且a的长度减一，这样就将原问题转化为上述1、2讨论的问题。
（4）a、b数组的长度有一个为0
当a、b数组的长度有一个为0时，直接返回另一个长度非0数组的第k个数即可。
综上所述
综上所述，我们在每次递归的时候都去除了一个数组中包含一个中位数的一半元素，直到一个数组被完全排除在外为止，直接去另一个数组的第k个数。上面的过程中由于每次总会去除一个中位数，因此算法总能够收敛，不难证明算法的时间复杂度为O(logN)。
代码
public class Main {
public static void main(String[] args) {
int[] a = {1, 2, 3, 6};
int[] b = {3, 6, 8, 9, 13};
Solution solution = new Solution();
System.out.print(solution.getKth(a, 0, a.length, b, 0, b.length, k));
}
}
class Solution {
public int getKth(int[] a, int aLeft, int aRight, int[] b, int bLeft, int bRight) {
//数组长度
int aLen = aRight - aLeft + 1;
int bLen = bRight - bLeft + 1;
//递归边界条件
if (a == null || b == null || aLen < 0 || bLen < 0 || k <= 0 || k > aLen + bLen) {
return -1;
}
//a b 长度为0
if (aLen == 0) {
return b[bLeft + k - 1];
}
if (bLen == 0) {
return a[aLeft + k - 1];
}
//a b 长度不为0，但k==1
if (k == 1) {
return Math.min(a[aLeft], b[bLeft]);
}
//长度一奇一偶，去掉最小值，长度同为奇数或者同为偶数
if ((aLen & 0x1) ^ (bLen & 0x1) == 1) {
if (a[aLeft] < b[bLeft]) { //此时k>1，不可能为最小值，所以去掉在这里的最小值，找Top k-1
return getKth(a, aLeft + 1, aRight, b, bLeft, bRight, k - 1);
} else {
return getKth(a, aLeft, aRight, b, bLeft + 1, bRight, k - 1);
}
}
int aMid, bMid;//长度，不是中间值的下标
if ((aLen & 0x1) == 1) { //两数组长度为奇数
aMid = aLen / 2;
bMid = bLen / 2;
} else { //两数组长度为偶数
aMid = aLen / 2 - 1;
bMid = bLen / 2;
}
//中点坐标
int aMidIndex = aLeft + aMid;//aMidIndex-aLeft+1=aMid+1
int bMidIndex = bLeft + bMid;
//两个数组长度为奇数时，a数组长度2*x+1，b数组长度为2*y+1，总数组长度和2*x+2*y+2，比较k与x+y+1关系
//两个数组长度为偶数时，a数组长度2*x+2，b数组长度为2*y，总数组长度为2*x+2*y+2，比较k与x+y+1关系
if (a[aMidIndex] <= b[bMidIndex]) {
if (k <= (aMid + bMid + 1)) {//舍弃b的后半段
return getKth(a, aLeft, aRight, b, bLeft, bMidIndex - 1, k);
} else {//舍弃a的前半段
return getKth(a, aMidIndex + 1, aRight, b, bLeft, bRight, k - aMid - 1);
}
} else {
if (k <= (aMid + bMid + 1)) {//舍弃a的后半段
return getKth(a, aLeft, aMidIndex - 1, b, bLeft, bRight, k);
} else {//舍弃b的前半段
return getKth(a, aLeft, aRight, b, bMidIndex + 1, bRight, k - bMid - 1);
}
}
}
}