两有序数组求第k大，复杂度O(lg m + lgn)

本文主要是介绍两有序数组求第k大，复杂度O(lg m + lgn)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

第k小
第k大

这里拿第k小分析：设两个数组为A[1…m],B[1…n]，则中间位置分别为m/2与n/2，假设A[m/2]>B[n/2]，那么A[m/2…m]在A+B的n/2+m/2之后，此时，若k<n/2+m/2，那么就可以排除A[m/2…m]的元素，在剩余元素再进行上述操作，若k>n/2+m/2，那么就可以排除B[1…n/2]的元素，再剩余元素中寻找第k-n/2小项。

第k小

#include <iostream>
using namespace std;int Search(int A[], int B[], int aLeft, int aRight, int bLeft, int bRight, int k)
{//偶数个元素则中间偏左，奇数个元素则中间那个int aMiddle = (aLeft + aRight) / 2;int bMiddle = (bLeft + bRight) / 2;// 退出条件if (aLeft > aRight)return B[bLeft + k - 1];if (bLeft > bRight)return A[aLeft + k - 1];// A的从左到中间的和B的从左到中间的总共的元素个数：n/2+m/2int half = (aMiddle - aLeft + 1) + (bMiddle - bLeft + 1);if (A[aMiddle] > B[bMiddle]){if (k <= half)return Search(A, B, aLeft, aMiddle - 1, bLeft, bRight, k);elsereturn Search(A, B, aLeft, aRight, bMiddle + 1, bRight, k - (bMiddle - bLeft) - 1);}else{if (k <= half)return Search(A, B, aLeft, aRight, bLeft, bMiddle - 1, k);elsereturn Search(A, B, aMiddle + 1, aRight, bLeft, bRight, k - (aMiddle - aLeft) - 1);}
}
int main(void)
{int A[3] = {1, 2, 3}, B[4] = {4, 5, 6, 7};int alen = sizeof(A) / sizeof(A[0]);int blen = sizeof(B) / sizeof(B[0]);int k = 3;printf("[第%d小元素] = %d\n", k, Search(A, B, 0, alen - 1, 0, blen - 1, k));return 0;
}

第k大

#include <iostream>
using namespace std;int Search(int A[], int B[], int aLeft, int aRight, int bLeft, int bRight, int k)
{//偶数个元素则中间偏左，奇数个元素则中间那个int aMiddle = (aLeft + aRight) / 2;int bMiddle = (bLeft + bRight) / 2;// 退出条件if (aLeft > aRight)return B[bLeft + k - 1];if (bLeft > bRight)return A[aLeft + k - 1];// A的从左到中间的和B的从左到中间的总共的元素个数：n/2+m/2int half = (aMiddle - aLeft + 1) + (bMiddle - bLeft + 1);if (A[aMiddle] > B[bMiddle]){if (k <= half)return Search(A, B, aLeft, aMiddle - 1, bLeft, bRight, k);elsereturn Search(A, B, aLeft, aRight, bMiddle + 1, bRight, k - (bMiddle - bLeft) - 1);}else{if (k <= half)return Search(A, B, aLeft, aRight, bLeft, bMiddle - 1, k);elsereturn Search(A, B, aMiddle + 1, aRight, bLeft, bRight, k - (aMiddle - aLeft) - 1);}
}
int main(void)
{int A[3] = {1, 2, 3}, B[4] = {4, 5, 6, 7};int alen = sizeof(A) / sizeof(A[0]);int blen = sizeof(B) / sizeof(B[0]);int k = 3;printf("[第%d大元素] = %d\n", k, Search(A, B, 0, alen - 1, 0, blen - 1, alen + blen + 1 - k));return 0;
}