求两个升序序列的中位数的最优算法

优雅的算法 TOMORROW 4个月前 (08-25) 407次浏览 0个评论 扫描二维码

设计一个在时间和空间两方面都尽可能高效的算法,找出两个升序序列 A 和 B 的中位数(也就是两个序列合起来的中位数),最优算法思想如下:

设 A、B 的长度为 n,中位数分别为 a、b;

  • 1)若 a=b,则 a 或 b 即为所求中位数算法结束;
  • 2)若 a<b,则舍弃 A 中较小的一半,同时舍弃序列 B 中较大的一半,要求两次舍弃的长度相等;        
    • 解释若 a<b,则说明 A 中较小的一半既比 A 中较大的一半小,也比 B 中较大的一半,也就是说 A 中较小的一半比 n 个数要小,而 AB 合并有 2n 个数,所以中位数不可能在 A 中较小一半中(临界问题暂时不考虑);同理,中位数不可能在 B 中较大的一半;
  • 3)若 a>b,则舍弃 A 中较大的一半,同时舍弃序列 B 中较小的一半,要求两次舍弃的长度相等;        
    • 解释同 2.

这样,求升序序列 A 和 B 的中位数,就变成了求被保留下来的两个升序序列的中位数了,这样就重复过程 1)、2)、3),直到两个序列中都只含一个元素时,较小的就是所求中位数。

 

算法源码实现

C 语言算法实现:

/*求两个升序序列的中位数*/
int m_search(int A[], int B[], int n )
{
	/*分别表示序列 A B 的首位数 末尾数 中位数*/
	int s1=0, d1=n-1, m1;     
	int s2=0, d2=n-1, m2;

	while(s1!=d1 || s2!=d2)
	{
		m1 = (s1+d1)/2;
		m2 = (s2+d2)/2;

		if(A[m1]==B[m2])/*满足条件 1*/
			return A[m1];

		if(A[m1]<B[m2])/*满足条件 2*/
		{
			if( (s1+d1)%2==0 )/*元素个数为奇数*/
			{
				s1=m1;/*舍弃 A 中间点以前的部分并保留中间点*/
				d2=m2;/*舍弃 B 中间点以后的部分并保留中间点*/
			}
			else/*元素个数为偶数*/
			{
				s1=m1+1;/*舍弃 A 中间点以前部分以及中间点*/
				d2=m2;/*舍弃 B 中间点以后部分并保留中间点*/
			}
		}
		else/*满足条件 3*/
		{
			if( (s2+d2)%2==0 )
			{
				d1=m1;
				s2=m2;
			}
			else
			{
				d1=m1;
				s2=m2+1;
			}
		}
	}

	return A[s1]<B[s2]? A[s1]:B[s2];
}

 

算法的时间复杂度为求两个升序序列的中位数的最优算法

 

空间复杂度为 O(1) 。

 

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:求两个升序序列的中位数的最优算法
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
能干的板栗发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到