多数组k大数 -- 二分思路
多数组k大数给定两个有序数组arr1和arr2,在给定一个整数k,返回两个数组的所有数中第K小的数。 arr1 = {1,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 = {0,1,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://www.voidcn.com/article/p-nabqeevw-wk.html 多数组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,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,kth - lenS,lenL - 1);
}
if (longArr[kth - lenS - 1] >= shortArr[lenS - 1]){
return longArr[kth - lenS - 1];
}
return getUpMedian(shortArr,kth - 1);
}
int getUpMedian(vector<int> arr1,int l1,int r1,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];
}
};
注意点:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |