问题: 现在有两个已经排好序的数组,要写一个算法求其中位数,要求算法的时间复杂度是O(n),空间复杂度是O(1),其中数组的长度是n.解法: 显然的,如果有我们设这两个数组是A[0......n-1],B[0......n-1],则我们比较A[(n-1)/2]与B[(n-1)/2]大小,如果前者大于后者,说明我们要找的中位数在A[0......(n-1)/2]和B[n/2,......n-1]之间;否则,说明我们要找的中位数在A[n/2......n-1]和B[0......(n-1)/2]之间,而这两个数组的元素个数又相同,对此可以递归处理。
//在此函数中,arrayA和arrayB是两个数组,ibeginA(B)和iendA(B)是数组的边界(取闭区间)
int middle(int arrayA[], int ibeginA, int iendA, int arrayB[], int ibeginB, int iendB)
{
if (ibeginA == iendA)
{
return arrayA[ibeginA];
}
int iMidAPos = (ibeginA + iendA) / 2;
int iMidBPos = (ibeginB + iendB) / 2;
int iMidAVal = arrayA[iMidAPos];
int iMidBVal = arrayB[iMidBPos];
if (iMidAVal > iMidBVal)
{
//去掉A的右边和B的左边
return middle(arrayA, ibeginA, iMidAPos-1, arrayB, iendB-(iMidAPos-ibeginA)+ 1, iendB);
}
else
{
//去掉A的左边和B的右边
return middle(arrayA, iendA-(iMidBPos-ibeginB)+1, iendA, arrayB, ibeginB, iMidBPos-1);
}
}
分享到:
相关推荐
【C++ 近序数组实现案例】
此段程序用了递归算法计算组合数在相应表中的序数。
无法定位序数处理方法,用管理员命令提示符
c语言实现的序数法全排列,结合组合数学上的算法
排列生成算法,序数法,C语言源代码 首先生成中介数,由中介数确定排列。
用序数法生成全排列,java语言,希望有帮助
算法:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = ...
matlab开发-从序数微分方程自动生成模拟模型。这个应用程序自动从一个ODE创建一个Simulink模型
解决eclipse_无法定位序数于动态链接库libeay32.dll
一年级上册2.2 基数的序数练习题及答案【西师大版】精选.doc
c代码-两有序数组合并排序--冒泡
幼儿园中班优质公开课数学以内的序数PPT课件.pptx
c代码-两有序数组合并排序--非冒泡
中班数学:5以内的序数.doc
很有趣的一个问题,解决了许多现实的问题。
按照自己的理解,从一些基本概念和显而易见的事实出发,推出求全排列的思路,纯属无聊而写着玩,如果有误,请指正,谢谢。