已知一个整数序列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  22

问题 已知一个整数序列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
0

最新回复(0)