求两个不等长有序数组的中位数!已知两个有序数组A和B分别有n1和n2个数字,求一个用O（logn1+logn2)的算法去
2个回答
这个比较不好讲清楚,先假设 A 和 B 都是升序的.
这个问题的关键在于给定 k,怎样找到 A 和 B 合并后的第 k 大元素.我们可以这样做：
1.把 A 平均分为前后两个部分,前部分有 x 个元素,后部分有 n1-x 个元素（由于 A 是有序的,所以后一部分的所有元素大于前一部分）.A[x] = A的后一部分的第一个元素.
2.同理把 B 也平均分成前后两个部分,前部分有 y 个元素,后部分有 n2-y 个元素.B[y] = B的后一部分的第一个元素.
3.由于两个数组都是被平均分割的,所以可以近似地认为 x = n1/2,y = n2/2.
这里不妨设 A[x] B[y] 处理过程和下面类似）：
以下是基于这个算法的程序,具体实现是在 element_at 这个函数中,通过调用 element_at(0,n1-1,0,n2-1,k) 可返回 A,B 数组合并后第 k 大的元素.
#include
int n1,n2;
int A[1000];
int B[1000];
int element_at(int l1,int r1,int l2,int r2,int k) {
int x = (l1 + r1) / 2,y = (l2 + r2) / 2;
if (l1 > r1) return B[l2+k-1];
if (l2 > r2) return A[l1+k-1];
if (A[x]
相关问题
