给定两个有序数组arr1和arr2，在给定一个整数k，返回两个数组的所有数中第K小的数。
例如：
arr1 = {1,2,3,4,5};
arr2 = {3,4,5};
K = 1;
因为1为所有数中最小的，所以返回1；
arr1 = {1,2,3};
arr2 = {3,4,5,6};
K = 4;
因为3为所有数中第4小的数，所以返回3；
要求：如果arr1的长度为N，arr2的长度为M，时间复杂度请达到O(log(min{M,N}))。
这题目的难度在于时间复杂度请达到O(log(min{M,N}))，参考http://www.cnblogs.com/diegodu/p/3790860.html可以达到O（log（M+N））
借助http://www.cnblogs.com/diegodu/p/4589847.html 求等长数组求中位数的方法能够实现。
举例，
arr1 1 ~ 10，
arr2 1‘ ~ 20’.
当kth = 7时，kth < min(s1,s2),
求两个数组的前K个元素的中位数即可，因为，第K个必然在两个数组的前K个元素中。
getUpMedian(arr1, 0, kth - 1, arr2, 0, kth - 1);
当kth = 26时，kth>max(s1,s2)
arr1 的1到5 是不可能的，就算5>20,也不过第25而已，不会是26.
arr2的 1’到15‘ 是不可能的，就算15’>10,也不过第25而已，不会是26.
所以排除了5+15个元素，arr1剩下5个，arr2剩下5个。
如果求剩下10个元素的上中位数，我们能得到第25大的，不是第26大，
所以，我们可以单独检验一下arr1 的6 和arr2的16‘是不是答案，
若是直接返回，不是的话又排除了两个，排除了22个，剩余8个，求上中位数第四个，加一起正好是第26个。
当kth = 16时，min(s1, s2)<kth<max(s1,s2)
arr1 无法排除，都有可能。
arr2的 1’~5‘排除，就算5’大于arr1的10，也不过是15。
arr2的 17‘~20’排除，17‘本来就排17了，最小也就是拍17。
所以arr2还剩下 6’ ~ 16‘ 11个元素，而arr1 有10个元素，
为了使用上中位数的算法，可以单独检测一下6’，若是返回，若不是淘汰，剩余的使用上中位数的算法。
http://www.nowcoder.com/profile/864393/test/231563/24588
class Solution {
public:
int getUpMedian(vector<int> arr1, vector<int> arr2) {
if(arr1.size() != arr2.size())
return -;
if(arr1.size() == )
return -;
return getUpMedian(arr1, , arr1.size() -,
arr2, , arr1.size() - );
}
int getUpMedian(const vector<int> & arr1, int start1, int end1,
const vector<int> & arr2, int start2, int end2)
{
//cout << "start1\t" << start1 << endl;
//cout << "end1\t" << end1 << endl;
//cout << "start2\t" << start2 << endl;
//cout << "end2\t" << end2 << endl;
if(start1 == end1)
{
return min(arr1[start1], arr2[start2]);
}
int size = end1 - start1 + ;
int halfSize;
if(size & 0x1 == 0x1)
{
halfSize = (size + )/;
}
else
{
halfSize = size/;
}
if(arr1[start1 + halfSize - ] == arr2[start2 + halfSize - ])
return arr1[start1 + halfSize - ];
else if(arr1[start1 + halfSize - ] > arr2[start2 + halfSize - ])
return getUpMedian(arr1, start1, start1 + halfSize - ,
arr2, end2-(halfSize-), end2);
else //if(arr1[start1 + halfSize - 1] > arr2[start2 + halfSize - 1])
return getUpMedian(arr1, end1-(halfSize-) , end1,
arr2, start2, start2 + halfSize -);
}
int findKthNum(vector<int> arr1, vector<int> arr2, int kth)
{
int size1 = arr1.size();
int size2 = arr2.size();
if(size1 > size2)
return findKthNum(arr2, arr1, kth);//ensure size1 < size2
if(kth <= size1)
return getUpMedian(arr1, , kth - , arr2, , kth - );
else if (kth <= size2 && kth > size1)
//i.e.s1 = 10, s2 = 20, kth = 14;
// for arr2, kth + 1 ~ size2(15 ~ 20) is impossibly answer
// for arr2, 1 ~ kth - size1 -1 (1 ~ 3) is impossibly answer
// so arr2 has 20 - 6 - 3 = 11 numbers, but arr1 has 10 numbers
// so jundge one element of arr2 firstly, the call getUpMedian
{
if(arr2[kth - size1 - ] >= arr1[size1 - ] )
return arr2[kth - size1 - ];
return getUpMedian(arr1, , size1-, arr2, kth-size1, kth-);
}
else //if (kth > size2)
//i.e.s1 = 10, s2 = 20, kth = 25;
// first 4(kth - s2 - 1) of arr1 is impossibly answer. so just remove them
// first 14(kth - s1 - 1) of arr2 is impossibly answer.so just remvoe them
// arr1 still has s1 - (kth - s2 - 1) = s1 + s2 - kth + 1 numbers (6)
// arr2 still has s2 - (kth - s1 - 1) = s1 + s2 - kth + 1 numbers (6)
// we removes 2 * kth - s1 - s2 -2 numbers, (18)
// now we junge if arr1[kth-s2-1] and arr2[kth-s1-1] is the answer,if not, we remother them
// then we removes 2 * kth - s1 - s2 numbers (20)
// and arr1 and arr2 both have s1 + s2 - kth numbers(5)
// we just calc upMedia of them and got the answer, 20 + 5 = 25
{
if(arr2[kth-size1-] >= arr1[size1-])
return arr2[kth-size1-];
if(arr1[kth-size2-] >= arr2[size2-])
return arr1[kth-size2-];
return getUpMedian(arr1, kth-size2, size1-, arr2, kth-size1, size2-);
}
}
};