2. 考研
  3. 已知一个整数序列A=(a0，a1，…，an+1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=x且m＞n／2(0≤pk＜n，1≤k≤m)，则称x为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，

已知一个整数序列A=(a0，a1，…，an+1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=x且m＞n／2(0≤pk＜n，1≤k≤m)，则称x为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，

admin2015-12-30  6
问题 已知一个整数序列A=(a0，a1，…，an+1)，其中0≤ai＜n(0≤i＜n)。若存在ap1=ap2=…=apm=x且m＞n／2(0≤pk＜n，1≤k≤m)，则称x为A的主元素。例如A=(0，5，5，3，5，7，5，5)，则5为主元素；又如A=(0，5，5，3，5，1，5，7)，则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法j找出A的主元素。若存在主元素，则输出该元素；否则输出-1。
要求：
给出算法的基本设计思想。
选项
答案给出算法的基本设计思想： 算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。 算法可分为以下两步： ①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复匕述过程，直到扫描完全部数组元素。 ②判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n／2，则为主元素；否则，序列中不存在主元素。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/7Kxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)