刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

主要成分

时间限制: 1000MS

内存限制: 65536KB

背景信息:

金星是离地球最近的行星,人类发射的“金星快车”探测器的主要任务是对金星大气层进行精确的探测,分析其化学成分。

题目描述:

从金星探测器传回来一组测量数据,这是一个长度为N(1≤N≤1000000)的整数数列,数列中的每个整数代表某一种化学成分(相同的整数代表相同的化学成分)。

主要成分:指在包含的所有化学成分中比例超过一半(N÷2的结果向下取整)的成分。

现在要判断其是否有主要成分;如果有,其主要成分是哪一种?

例如:

当N=7,整数数列为1 2 3 2 2 1 2,其中成分2有4个,超过了7的一半(7的一半向下取整为3),所以主要成分是2。

当N=6,整数数列为1 102 31 31 1 102,其中的每一种成分都只有2个,未超过6的一半(6的一半为3),所以没有主要成分。

输入描述

第一行输入一个正整数N(1≤N≤1000000),表示数列长度

第二行输入N个整数(1≤整数≤2×109),每个整数表示一种化学成分,两个整数之间用一个空格隔开

输出描述

输出一行,如果存在主要成分,则输出代表主要成分的整数,否则,输出No


样例输入

7

1 2 3 2 2 1 2

样例输出

2

使用微信搜索喵呜刷题,轻松应对考试!

答案:

2

解析:

【喵呜刷题小喵解析】:
根据题目描述,我们需要判断数列中是否存在主要成分,即比例超过一半的成分。如果存在,我们需要找出这种成分。

首先,我们需要统计每个成分的数量。可以使用一个哈希表来记录每个成分出现的次数。遍历输入的数列,每次遇到一个成分,就在哈希表中对应的计数器上加1。

然后,我们计算数列长度的一半(N÷2的结果向下取整)。遍历哈希表中的每个计数器,如果某个计数器的值大于数列长度的一半,那么我们就找到了主要成分,输出对应的成分即可。

如果不存在任何一个计数器的值大于数列长度的一半,那么就没有主要成分,输出"No"。

在本题中,输入的数列长度为7,数列中的成分有1、2、3,其中成分2出现了4次,超过了7的一半(7的一半向下取整为3),所以主要成分是2,输出2即可。
创作类型:
原创

本文链接:主要成分 时间限制: 1000MS 内存限制: 65536KB 背景信息: 金星是离地球最近的行星,

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share