#include <iostream>
using namespace std;
int get_median(int a[],int begin1,int end1,int b[],int begin2,int end2,int k){
if(begin1>end1){ //在数组A中无法找到
return get_median(b,begin2,end2,a,begin1,end1,k);
}
int t = (begin1+end1)/2;
if(a[t]>=b[k-t-1]&&a[t]<=b[k-t]){//got it
return a[t];
}else if(a[t]<b[k-t-1]){//too small
return get_median(a,t+1,end1,b,begin2,end2,k);
}else if(a[t]>b[k-t]){//too big
return get_median(a,begin1,t-1,b,begin2,end2,k);
}
return -1;
}
double getMedian(int a[],int m,int b[],int n){
if((m+n)%2==0){//偶数 中位数的值等于下中位数和上中位数的平均值
//下中位数 前共有 (m+n)/2-1 个数
//上中位数 前共有 (m+n)/2 个数
int k= (m+n)/2;
int lm = get_median(a,0,m-1,b,0,n-1,k-1);
int hm = get_median(a,0,m-1,b,0,n-1,k);
return (double)(lm+hm)/2;
}else{ //奇数
int k= (m+n)/2;
return get_median(a,0,m-1,b,0,n-1,k);
}
}
int main(){
int a[]={1,3,4,5};
int b[]={2,6,7,8};
cout<<getMedian(a,4,b,4)<<endl;
return 0;
}
分享到:
相关推荐
(1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...
给定两个有序数组a b 使合并后的数组仍然有序 归并算法的事件复杂度为O logn
17082 两个有序数序列中找第k小(必做) 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: C++;C;VC;JAVA Description 已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为...
已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。
时间复杂度为O(logN)的常用算法,算法数据结构 五大常用算法
二分查找,因为数组有序,可以利用二分查找,时间复杂度O(logn)。 分析步骤: 1. 如果第一个数为正数,说明整个数组没有负数,直接返回第一个数 2. 如果最后一个数为负数,说明整个数组没有正数,直接返回最后一个...
设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数。试设计一个O(logn)时间的算法,找出X和Y的2n个数的中位数
深入浅出,描述java算法,从0到1。 1.大O表示法:粗略的量度方法即算法的速度是如何与数据项的个数相关的 算法 大O表示法表示的运行时间 ...O(1)是最优秀的,O(logN)良好,O(N)还可以,O(N2)稍差(在冒泡法中见到)
求2n个数的中位数,设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数。试设计一个O(logn)时间的算法,找出X和Y的2n个数的中位数
既然有时间复杂度更小的算法,我们容易想到二分查找,因为它的时间复杂度为O(logn)。这个问题是否可以运用二分查找呢?答案是肯定的。观察一下数组的特性,首先递增(称为递增a),然后突然下降到最小值,然后再递增...
现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。 此题请勿采用将序列X和Y合并找第k小的O(m+n)的一般方法,要充分利用X和Y已经排好序的这一特性。 输入格式 第一行有三个数,...
快速幂 基于java实现的快速幂、快速乘算法,利用二进制位运算将O(n)的算法复杂度降到O(logn)
已知(k1, k2, …, kp)是堆,则可以写一个时间复杂度为O(logn)的算法,将(k1, k2, …, kp, kp+1)调整为堆。试编写“从p=1起,逐个插入建堆”的算法,并讨论由此方法建堆的时间复杂度。
| RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA 19 | LCA 离线算法 O(E)+O(1) 20 | 带权值的并查集 20 | 快速排序 20 | 2 台机器工作调度 20 | 比较高效的大数 20 | 普通的大数运算 21 | 最长公共递增子序列 O(N^2) ...
我们常常会遇到这样的问题:给定一个有序数组a\left[N\right],需要查找出最大的不小于某个数的数字或者查找出最小的大于某个数的数字,通常的朴素做法是从头到尾遍历一遍,那么时间复杂度就是O\left(n\right)。...
时间复杂度为O(logN)的排序算法。。俗称重口味排序
给定一个无重复元素的数组A[0…N-1],求找到一个该数组的局部最大值。规定:在数组边界外的值无穷小。即:A[0]>A[-1],A[N-1] >A[N]。 显然,遍历一遍可以找到全局最大值,而全局最大值显然是局部最大值。 可否有...
算法的特性:输入输出、有穷性、确定性、可行性。 时间复杂度:T(n)=O(f(n))。...常用的时间复杂度所耗费的时间从小到大依次是:O(1)<O(logn)<O(n)<O(n logn)<O(n²)<O(n³)<O(2的n次方)<O(n!)<O(n的n次方)
快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)