文章
101
粉丝
0
获赞
1
访问
30.5k
(1)采用一个辅助数组大小为b[n],遍历a[n],将a[i]出现的次数依次存入b[a[i]]中,之后遍历b[i],寻找其最大元素,若其最大元素>n/2,则对应下标+1即为主元素,否则输出-1
(2)int b[n]=0;
int result=0;
int false=-1;
for(int i=0;i<n;i++)
{
b[a[i]]++;
}
for(int i=0;i<n;i++)
{
int max1=0;
if(b[i]>max1) b[i]=max1;result=i+1;
}
if(max1>n/2)cout<<result;
else cout<<false;
(3)时间复杂度与空间复杂度均为O(n)
评分及理由
(1)得分及理由(满分4分)
得分:2分
理由:学生的基本设计思想是使用辅助数组统计每个元素的出现次数,然后找出出现次数最多的元素并判断是否超过n/2。这种方法思路正确,能够解决问题,但并不是题目要求的"尽可能高效的算法"。标准答案使用的是Boyer-Moore投票算法,时间复杂度O(n),空间复杂度O(1),而学生的方案空间复杂度为O(n),不符合"尽可能高效"的要求。因此扣2分。
(2)得分及理由(满分7分)
得分:3分
理由:学生的代码实现存在多处逻辑错误:
1. 变量max1在每次循环中都初始化为0,无法正确记录最大值
2. 赋值语句"b[i]=max1"逻辑错误,应该是"max1=b[i]"
3. 变量result的赋值位置错误,应该在找到最大值时记录
4. 缺少对数组b的初始化(虽然思路中提到但代码未体现)
5. 输出格式不完整
虽然基本思路正确,但由于存在多处逻辑错误,严重影响了算法的正确性,因此扣4分。
(3)得分及理由(满分2分)
得分:2分
理由:学生正确分析了算法的时间复杂度和空间复杂度,均为O(n),这与学生所采用的算法思路是一致的,因此给满分。
题目总分:2+3+2=7分
登录后发布评论
暂无评论,来抢沙发