早教吧作业答案频道 -->数学-->
求两个不等长有序数组的中位数!已知两个有序数组A和B分别有n1和n2个数字,求一个用O(logn1+logn2)的算法去找A和B组合后的中位数!
题目详情
求两个不等长有序数组的中位数!
已知两个有序数组A和B分别有n1和n2个数字,
求一个用O(logn1+logn2)的算法去找A和B组合后的中位数!
已知两个有序数组A和B分别有n1和n2个数字,
求一个用O(logn1+logn2)的算法去找A和B组合后的中位数!
▼优质解答
答案和解析
这个比较不好讲清楚,先假设 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]
这个问题的关键在于给定 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]
看了求两个不等长有序数组的中位数!...的网友还看了以下:
英语固定句型不可以分开的吧过去将来完成时态wouldhavedone就不能像这样Hesaidhew 2020-04-08 …
在英语句子中如果没有明确的过去时态标志词是否也可以用一般过去时?如weplayedgames无过去 2020-04-08 …
15、下列做法可以达到预期目的的是()A、用稀盐酸除去小刀上的铁锈B、用点燃的方法除去CO2中混有 2020-04-08 …
saw跟seen有什么不一样?saw是SEE的过去式,SEEN也是SEE的过去式,他们两个有什么不 2020-04-26 …
lose的过去式和过去分词是lost,那么请问为什么我们经常在文章里看到的都是lose的过去式呢? 2020-05-02 …
下列实验能达到目的的是()A.用CCl4萃取碘水中的碘B.将足量盐酸加入混有少量CaCO3杂质的N 2020-05-13 …
暑假,我们可以放下书本,背起行囊,行走四方,过一种别样的生活----读自己爱读的书,去自己想去的地 2020-05-14 …
现在,你看到7/10,有多少种理解呢? 1.从分数的意义去理解: 2.从除法的角度去理解: 3.从 2020-05-16 …
英语翻译只有思想和精神得到升华,才能有更多的人去关心和拯救这个世界.努力探索科学,生命等一切价值, 2020-05-17 …
英语翻译1只有思想和精神得到升华,才能有更多的人去关心和拯救这个世界.努力探索科学,生命等一切价值 2020-05-17 …