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  45
问题 已知一个整数序列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。
要求：
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
选项
答案算法实现： int Majority(int A[]，int n){ int i，c，count=1；／／c用来保存候选主元素，count用来计数 c=A[0]；／／设置A[0]为候选主元素 for(i=1；i＜n；i++)／／查找候选主元素 if(A[i]==c) count++；／／对A中的候选主元素计数 else if(count＞0)／／处理不是候选主元素的情况 count--； else{／／更换候选主元素，重新计数 C=A[i]； count=1； } if(count＞0) for(i=count=0；i＜n；i++)／／统计候选主元素的实际出现次数 if(A[i]==c) count++； if(count＞n／2)return c；／／确认候选主元素 else return -1；／／不存在主元素 }
解析
转载请注明原文地址:https://kaotiyun.com/show/KKxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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