计算机考研408羊驼老师+每日一题+ 算法真题解析 DAY 89

发布于 2021-08-08 13:45 ，所属分类：试题库考试资料大全

带你一起上岸


羊驼小课堂


算法真题解析 DAY 89


05


已知一个整数序列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）说明你所设计算法的时间复杂度和空间复杂度。


点击空白处查看答案

（1）给出算法的基本设计思想：

算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素 Num。然后重新计数，确认 Num 是否是主元素。算法可分为以下两步：

① 选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数 Num 保存到 c 中，记录 Num 的出现次数为 1；若遇到的下一个整数仍等于 Num，则计数加 1，否则计数减 1；当计数减到 0 时，将遇到的下一个整数保存到 c 中，计数重新记为 1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

② 判断 c 中元素是否是真正的主元素：再次扫描该数组，统计 c 中元素出现的次数，若大于 n/2，则为主元素；否则，序列中不存在主元素。



视频解析


点击边框调出视频工具条




计算机考研408羊驼

号｜Alpaca408

QQ群 | 431364494

新浪微博、B站｜计算机考研408羊驼老师

相关资源