题目描述：
给定两个有序数组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}))。
1 /* 2 思路：利用上一题NowClass3-4-GetUpMedian的求上中位数的思路进行求解。 3 arr1和arr2，其中数组长度分别为：lenS和lenL（lenS<=lenL） 4 分情况分析： 5 1) kth <= lenS; 6 只需求arr1和arr2的前kth个数的上中位数即可。 7 即：findProcess(arr1, 0, kth-1, arr2, 0, kth-1). 8 2) kth > lenL; 9 arr1中前kth-lenL-1个数不可能是第kth个数， 10 arr2中前kth-lenS-1个数不可能是第kth个数， 11 此时，arr1中剩余(lenS-(kth-lenL-1))=lenS+lenL+1-kth个可能的数， 12 arr2中剩余(lenL-(kth-lenS-1))=lenL+lenS+1-kth个可能的数。剩余个数相同。 13 然后，先判断arr1中的第kth-lenL-1个数是否大于arr2的最后一个数， 14 如果是则直接返回arr1的第kth-lenL-1个数即可。 15 再判断arr2中的第kth-lenS-1个数是否大于arr1的最后一个数， 16 如果是则直接返回arr2的第kth-lenS-1个数。 17 否则求arr1的(kth-lenS,lenS)和arr2的(kth-lenL,lenL)的上中位数。 18 即：findProcess(arr1,kth-lenS,lenS,arr2,kth-lenL,lenL). 19 3) lenS < kth <= lenL; 20 arr1中lenS个数都有可能， 21 arr2中(0, kth-1-lenS-1)和(kth-1,lenL-1)不可能，此时剩余kth-1-(kth-1-lenS-1)=lenS+1个数 22 然后，单独对地kth-lenS-1验证，是否大于arr1的最后一个数，如果是则直接返回该数； 23 否则，求arr1的(0,lenS-1)和arr2的(kth-lenS,kth-1)个数求上中位数。 24 即：findProcess(arr1,0,lenS-1,arr2, kth-lenS, kth-1). 25 */ 26 27 #include28 #include 29 using namespace std; 30 31 // 查找两个数组的上中位数。 32 int findProcess(vector arr1, int l1, int r1, vector arr2, int l2, int r2){ 33 if (l1 == r1) 34 return (arr1[l1] < arr2[l2] ? arr1[l1] : arr2[l2]); 35 // 元素个数为奇数，则offset=0；否则offset=1. 36 int offset = ((r1-l1+1)&1) ^ 1; 37 int mid1 = (l1+r1)/2; 38 int mid2 = (l2+r2)/2; 39 if (arr1[mid1] > arr2[mid2]) 40 return findProcess(arr1, l1, mid1, arr2, mid2+offset, r2); 41 else if(arr1[mid1] < arr2[mid2]) 42 return findProcess(arr1, mid1+offset, r1, arr2, l2, mid2); 43 else 44 return arr1[mid1]; 45 } 46 47 int findKthNum(vector arr1, vector arr2, int kth){ 48 if (kth <= 0 || kth > arr1.size()+arr2.size()) 49 exit(-1); 50 vector arrS = arr1.size() < arr2.size() ? arr1 : arr2; 51 vector arrL = arr1.size() < arr2.size() ? arr2 : arr1; 52 int lenS = arrS.size(); 53 int lenL = arrL.size(); 54 if (kth <= lenS) 55 return findProcess(arrS, 0, kth-1, arrL, 0, kth-1); 56 else if (kth > lenL){ 57 if (arrS[kth-lenL-1] >= arrL[lenL-1]) 58 return arrS[kth-lenL-1]; 59 else if (arrL[kth-lenS-1] >= arrS[lenS-1]) 60 return arrL[kth-lenS-1]; 61 else 62 return findProcess(arrS, kth-lenL, lenS-1, arrL, kth-lenS, lenL-1); 63 } 64 else{ 65 if (arrL[kth-lenS-1] >= arrS[lenS-1]) 66 return arrL[kth-lenS-1]; 67 else 68 return findProcess(arrS,0,lenS-1,arrL, kth-lenS, kth-1); 69 } 70 } 71 72 int main(){ 73 vector a1; 74 a1.push_back(1); 75 a1.push_back(1); 76 a1.push_back(1); 77 a1.push_back(2); 78 a1.push_back(3); 79 a1.push_back(4); 80 81 a1.push_back(6); 82 a1.push_back(6); 83 a1.push_back(6); 84 85 a1.push_back(8); 86 a1.push_back(8); 87 a1.push_back(8); 88 89 a1.push_back(10); 90 a1.push_back(10); 91 a1.push_back(10); 92 a1.push_back(11); 93 a1.push_back(12); 94 a1.push_back(18); 95 a1.push_back(19); 96 97 vector a2; 98 a2.push_back(11); 99 a2.push_back(19);100 a2.push_back(21);101 a2.push_back(33);102 a2.push_back(42);103 a2.push_back(50);104 a2.push_back(50);105 cout << findKthNum(a1,a2,19) << endl;106 return 0;107 }