(13分)已知一个整数序列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 个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出A 的主元素。若存在主元素,则输出该元素;否则输出-1。要求:
(1)给出算法的基本设计思想。
(2)根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
查看答案和解析【25考研辅导课程推荐】:25考研集训课程,VIP领学计划,25考研VIP全科定制套餐(公共课VIP+专业课1对1) , 这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE