`
vearne
  • 浏览: 18870 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

两个有序数组求中位数的O(logn)算法

 
阅读更多

#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个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...

    find_the_middle_number.rar_Middle C

    在给定的“find_the_middle_number.rar_Middle C”压缩包文件中,涉及的主要知识点是寻找两个有序数组的中位数。这个问题是一个经典的算法问题,它要求在O(logn)的时间复杂度内解决,其中n是数组元素的数量。在描述...

    分治算法举例.pdf

    归并排序在合并两个有序子数组时,可以统计出在合并过程中逆序对的数量。设f(i,j)为从i到j的逆序对数量,s(i,j,k)为以k为分割点的逆序对数量。通过递归公式,我们可以计算出总的逆序对数。同样,由于每次操作都将...

    找中位数1

    【标题】:“找中位数1”通常是指在数据处理和算法设计中寻找一组数值的中位数问题。中位数是一组数据有序排列后位于中间位置的数值,当数据量为奇数时,它是正中间的那个数;当数据量为偶数时,中位数是中间两个数...

    C语言 归并排序

    归并排序的核心思想是将待排序的数组分成两部分,分别对这两部分进行排序,然后将两个有序数组合并成一个整体有序的数组。具体步骤如下: 1. **分割**:将数组分成两个或多个较小的子数组。 2. **递归排序**:递归地...

    分治算法举例.docx

    这个问题的目标是在两个已排序的数组X和Y中找到它们合并后的中位数,且要求时间复杂度为O(logn)。我们利用分治策略和二分查找法来解决。首先,我们找到每个数组的中间元素,根据它们的相对大小关系,我们可以确定中...

    逆序对(树状数组) C语言

    逆序对是排序数组中的一种概念,它是指在数组中,如果两个元素a和b的值满足a &gt; b,但它们的下标i ,则称(a, b)为一个逆序对。逆序对的数量可以反映出数组的有序程度,是许多算法问题的基础,如快速排序、归并排序等...

    算法考试1

    通过比较数组中位数,我们可以缩小搜索范围,最终在O(logn)的时间复杂度内找到中位数。分治法也被用于计算逆序对的数量,如题目所示,通过类似归并排序的过程,将数组分为两半,递归地计算逆序对,再进行合并,其...

    算法学习笔记.pdf

    二分查找是用于在有序数组中查找特定元素的算法,时间复杂度为O(logn)。它通过比较数组中间元素与目标值的大小,来决定下一步是查找左半部分还是右半部分,直到找到目标值或子序列为空。 四、二分搜索相关算法 高...

    查找第K小的元素 _ isnowfy1

    该算法将数组分成大小为5的子数组,计算每个子数组的中位数,接着找到这些中位数的中位数作为枢轴。由于中位数的中位数具有良好的分割特性,可以确保最坏情况下的分割比例为3:7或7:3,这保证了即使在最坏情况下,...

    排序算法的实现

    归并排序通常采用递归的方式实现,首先递归地对数组进行拆分,然后将两个有序的子数组合并成一个有序数组。 #### 时间复杂度与空间复杂度 - **时间复杂度**:O(nlogn)。 - **空间复杂度**:O(n),需要额外的空间来...

    课程设计2

    具体要求是在新数加入时保持时间复杂度为O(logN),而在获取中位数时保持时间复杂度为O(1)。这是一个典型的在线算法问题,需要在数据不断流入时高效地处理。 首先,我们分析了简单的线性结构,如顺序存储和链式存储...

    ACM/ICPC常用算法的代码库(吉林大学版,强烈推荐)

    - **二分查找**:在有序数组中查找特定元素的位置。 - **二分查找(大于等于V的第一个值)**:查找第一个大于等于给定值的元素位置。 - **所有数位相加**:计算一个整数中所有数字的总和。 #### Number数论 - **递...

    常用算法代码

    - **GRAHAM 求凸包 O(N * LOGN)**:Graham 算法用于求解凸包问题。 - **判断线段相交**:判断两条线段是否相交。 - **求多边形重心**:计算多边形的质心。 - **三角形几个重要的点**:介绍三角形中的一些特殊点。 - ...

    算法题常用lips1

    - **集合并集**:可以使用 `std::set_union()` 求两个集合的并集,结果可以直接输出或存储到另一个集合中。 - **集合差集**:使用 `std::set_difference()` 查找两个集合的元素差异。 - **集合交集**:使用 `std:...

    ACM/ICPC算法大全(c语言)

    - 二分查找是一种在有序数组中查找特定元素的高效算法。 - **所有数位相加** - 如何求解一个数字的所有位上的数字之和。 #### 数论(Number Theory) - **递推求欧拉函数PHI(I)** - 欧拉函数φ(n)是指小于n的正...

    基础算法 第7章 分治算法(C++版)-2021.02.04.pdf

    采用二分搜索的策略,每次选择中位数进行猜测,如果猜测的数字太大,则在较小的区间内继续猜测,反之则在较大的区间内猜测。通过这种方式,区间的大小逐渐减半,直到找到目标数字。 分治算法不仅应用于简单的搜索...

    东北大学算法程序与设计考试题

    首先将两个序列合并为一个有序序列,然后找到中位数。为了提高效率,可以采用二分查找的方法,逐步缩小候选中位数的范围。具体步骤如下: 1. **初始化**:设定两个指针分别指向两个序列的起始位置。 2. **比较**...

    NOIP算法模板(pascal版)

    - 返回x的任意一个数组下标:在有序数组中找到元素x的一个下标。 - 返回x的第一个位置或最后一个位置:找到元素x在序列中首次或最后一次出现的位置。 #### 3. 数据生成 该部分介绍了随机生成数据的方法,这对于测试...

Global site tag (gtag.js) - Google Analytics