多数组k大数

给定两个有序数组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}))。

http://www.nowcoder.com/practice/952b97f197494378a437c1f11596dc63?tpId=49&tqId=29339&rp=4&ru=/ta/2016test&qru=/ta/2016test/question-ranking

---

多数组中位数

给定两个有序数组arr1和arr2，两个数组长度都为N，求两个数组中所有数的上中位数。 例如： arr1 = {1,2,3,4}; arr2 = {3,4,5,6}; 一共8个数则上中位数是第4个数，所以返回3。

arr1 = {0,1,2}; arr2 = {3,4,5}; 一共6个数则上中位数是第3个数，所以返回2。

要求：时间复杂度O(logN)

http://www.nowcoder.com/practice/c001f4e9820447189110da5e882aa158?tpId=49&tqId=29340&rp=4&ru=/ta/2016test&qru=/ta/2016test/question-ranking

---

寻找最小的k个数(进一步要求顺序与原数组中元素顺序一致)

http://blog.csdn.net/qq_26437925/article/details/51719831

---

多数组k大数 AC代码

class Solution { public: int findKthNum(vector<int> arr1, vector<int> arr2, int kth) { int len1 = arr1.size(); int len2 = arr2.size(); vector<int> shortArr = len1 < len2 ? arr1 : arr2; vector<int> longArr = len1 >= len2 ? arr1 : arr2; int lenS = shortArr.size(); int lenL = longArr.size(); if (kth < 1 || kth > len1 + len2) // kth不符合 直接返回 return -1; if (kth <= lenS){ return getUpMedian(shortArr, 0, kth - 1, longArr, 0, kth - 1); } if (kth > lenL){ if (shortArr[kth - lenL - 1] >= longArr[lenL - 1]){ return shortArr[kth - lenL - 1]; } if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){ return longArr[kth - lenS - 1]; } return getUpMedian(shortArr, kth - lenL, lenS - 1, longArr, kth - lenS, lenL - 1); } if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){ return longArr[kth - lenS - 1]; } return getUpMedian(shortArr, 0, lenS - 1, longArr, kth - lenS, kth - 1); } int getUpMedian(vector<int> arr1, int l1,int r1,vector<int> arr2,int l2,int r2) { /* int N1 = arr1.size(); int N2 = arr2.size(); int l1 = 0, r1 = N1 - 1; int l2 = 0, r2 = N2 - 1;*/ while (l1 != r1 || l2 != r2) { int mid1 = (l1 + r1) / 2; int mid2 = (l2 + r2) / 2; // 表示 2分查找要不要包含中间那个数 奇数是0，偶数是1 int offset = (r1 - l1 + 1) & 1 ^ 1; if (arr1[mid1] > arr2[mid2]) { l2 = mid2 + offset; r1 = mid1; } else if (arr2[mid2] > arr1[mid1]){ l1 = mid1 + offset; r2 = mid2; } else{ return arr1[mid1]; } }// while return arr1[l1] < arr2[l2] ? arr1[l1] : arr2[l2]; } };

注意点：

求中位数 采用了二分思路

求中位数 用二分是 要注意长度为奇偶是不一样的（middle位置的数要不要取的问题），还要注意最后的处理

在求第k大数时，要分情况，淘汰掉一些显然不满足的情况，转换为求中位数问题，这里需要对k的大小分类讨论，见代码. 下面是其中一种情况的说明

Median of Two Sorted Arrays（leetcode）

ac代码， 借助多数组k大数

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int N1 = nums1.size(); int N2 = nums2.size(); int total = N1 + N2; double ans = 0; if (total == 0) return ans; if (N1 == 0) { if (N2 % 2 == 1) ans = nums2[N2 / 2]; else ans = 0.5 *(nums2[N2 / 2] + nums2[N2 / 2 - 1]); return ans; } if (N2 == 0) { if (N1 % 2 == 1) ans = nums1[N1 / 2]; else ans = 0.5 *(nums1[N1 / 2] + nums1[N1 / 2 - 1]); return ans; } if (total % 2 == 1) // 总共是奇数长度 { int k = total / 2 + 1; ans = findKthNum(nums1, nums2, k); } else{ int k1 = total / 2; int k2 = k1 + 1; ans = 0.5 * (findKthNum(nums1, nums2, k1) + findKthNum(nums1, nums2, k2)); } return ans; } int findKthNum(vector<int> arr1, vector<int> arr2, int kth) { int len1 = arr1.size(); int len2 = arr2.size(); vector<int> shortArr = len1 < len2 ? arr1 : arr2; vector<int> longArr = len1 >= len2 ? arr1 : arr2; int lenS = shortArr.size(); int lenL = longArr.size(); if (kth < 1 || kth > len1 + len2) // kth不符合 直接返回 return -1; if (kth <= lenS){ return getUpMedian(shortArr, 0, kth - 1, longArr, 0, kth - 1); } if (kth > lenL){ if (shortArr[kth - lenL - 1] >= longArr[lenL - 1]){ // 长度小的数组 所有元素都大于 长度大的数组 return shortArr[kth - lenL - 1]; } if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){ // 长度大的数组 所有元素都大于 长度小的数组 return longArr[kth - lenS - 1]; } // 淘汰掉不符合的 得到中位数即可 return getUpMedian(shortArr, kth - lenL, lenS - 1, longArr, kth - lenS, lenL - 1); } if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){ // kth在 longArr中 return longArr[kth - lenS - 1]; } // 淘汰掉 longArr中不符合的部分 return getUpMedian(shortArr, 0, lenS - 1, longArr, kth - lenS, kth - 1); } int getUpMedian(vector<int> arr1, int l1, int r1, vector<int> arr2, int l2, int r2) { /* int N1 = arr1.size(); int N2 = arr2.size(); int l1 = 0, r1 = N1 - 1; int l2 = 0, r2 = N2 - 1;*/ while (l1 != r1 || l2 != r2) { int mid1 = (l1 + r1) / 2; int mid2 = (l2 + r2) / 2; // 表示 2分查找要不要包含中间那个数 奇数是0，偶数是1 int offset = (r1 - l1 + 1) & 1 ^ 1; if (arr1[mid1] > arr2[mid2]) { l2 = mid2 + offset; r1 = mid1; } else if (arr2[mid2] > arr1[mid1]){ l1 = mid1 + offset; r2 = mid2; } else{ return arr1[mid1]; } }// while return arr1[l1] < arr2[l2] ? arr1[l1] : arr2[l2]; } };