专栏首页刷题笔记2-6 两个有序序列的中位数 (20 分)

2-6 两个有序序列的中位数 (20 分)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/shiliang97/article/details/101025378

2-6 两个有序序列的中位数 (20 分)

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,即第⌊(N+1)/2⌋个数(A​0​​为第1个数)。

输入格式:

输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4

输入样例2:

6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1

想半天,其实就是把两个数组存进去,找中间那个就行,并集也不是去重啥的,都不需要,直接做就行了。

缩短的代码有点别扭,但是有效代码行数控制在7行

#include<iostream>
using namespace std;
int a[200005];
int main(){
	int n,ai=0,bi;
	cin>>n;bi=n;
	for(int i=0;i<2*n;i++){cin>>a[i];}
	while(ai+bi-n<(2*n-1)/2){
		if(a[ai]>a[bi]) bi++;
		else ai++;}
	cout<<(a[ai]>a[bi]?a[bi]:a[ai]);
	return 0;
}

AC代码

#include<iostream>
using namespace std;
int a[100005],b[100005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}for(int i=0;i<n;i++){
		cin>>b[i];
	}int ai=0,bi=0;
	while(ai+bi<(2*n-1)/2){
		if(a[ai]>b[bi]) bi++;
		else ai++;}
	cout<<(a[ai]>b[bi]?b[bi]:a[ai]);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】16. 最接近的三数之和

    给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假...

    韩旭051
  • 【LeetCode】62. 不同路径

    一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

    韩旭051
  • 【LeetCode每日打卡】面试题56 - I. 数组中数字出现的次数

    一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    韩旭051
  • Linux Shell(一)——Shell变量

    1 变量的分类 在Linux中,变量分为环境变量 和 局部变量。 环境变量能被子进程继承,而局部变量只能在当前进程中使用。 并且,不论是环境变量还是局...

    大闲人柴毛毛
  • SQLServer中的CTE通用表表达式

      开发人员正在研发的许多项目都涉及编写由基本的 SELECT/FROM/WHERE 类型的语句派生而来的复杂 SQL 语句。其中一种情形是需要编写在 FROM...

    张传宁老师
  • 数据库语句练习

    (31)在Visual FoxPro中,以下有关SQL的SELECT语句的叙述中,错误的是______。 A.SELECT子句中可以包含表中的列和表达式 B...

    阳光岛主
  • 【SQL揭秘】有多少种数据库,就有多少类CTE

    Common Table Expression Common table expression简称CTE,由SQL:1999标准引入,可以认为是在单个 SEL...

    数据和云
  • 基于OpenCV与Dlib的行人计数开源实现

    PyImageSearch昨天发布的行人计数的Blog,详述了使用OpenCV和Dlib库中的检测和跟踪算法如何完成该功能。原网址开源代码需要F-Q才能下载,我...

    CV君
  • WordPress设置评论到达一定数量后自动关闭评论功能

    一些特殊的WordPress 站点可能需要对用户评论进行某些特殊情况的限制,比如本文要说的当评论到达一定数量后自动关闭评论功能,或者说评论一定天数后自动关闭评论...

    Jeff
  • python的一致性算法hash_rin

    下载地址:https://pypi.python.org/pypi/hash_ring/

    py3study

扫码关注云+社区

领取腾讯云代金券