（1）设置一个辅助数组长度为b[n+1],用于统计A中各个元素出现次数，遍历A，每次将b[A[i]]++,表示元素出现次数，遍历结束后，遍历b,记录b中出现的元素最大值下标与数值，若该数值大于n/2，输出下标，否则输出-1
(2)初始化数组a,b;
int SelectmainEl(int a[n],int b[n+1])
{
for(int i=0;i<n;i++) b[a[i]++];//更新b数组
int max1=0,int result=0;
for(int i=0;i<n+1;i++)
{if(b[i]>max1){max1=b[i];result=i}//记录最大出现次数及其下标
if(max1>n/2) return result;
else return -1
}
评分及理由
（1）得分及理由（满分4分）
得分：2分
理由：学生的基本设计思想是使用辅助数组统计每个元素的出现次数，然后找出出现次数最多的元素并判断是否超过n/2。这种方法虽然正确，但并不是题目要求的"尽可能高效的算法"，因为需要O(n)的额外空间。标准答案使用的是Boyer-Moore投票算法，空间复杂度为O(1)。学生的思路正确但不够优化，因此扣2分。
（2）得分及理由（满分7分）
得分：4分
理由：代码实现存在以下问题：
1. 函数参数定义不规范，数组长度n应该作为参数传入
2. 语法错误：b[a[i]++]应该是b[a[i]]++
3. 逻辑错误：第二个循环中，if(max1>n/2) return result; else return -1应该放在循环外部，否则只检查第一个元素就返回
4. 代码结构不完整，缺少必要的初始化
5. 注释缺失
由于思路正确但实现存在较多问题，扣3分。
（3）得分及理由（满分2分）
得分：1分
理由：学生没有明确说明算法的时间复杂度和空间复杂度。根据其算法思路，时间复杂度为O(n)，空间复杂度为O(n)。由于没有明确说明，扣1分。
题目总分：2+4+1=7分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发