文章
59
粉丝
0
获赞
0
访问
9.0k
1.维护一个长度为2的滑动窗口,当窗口中有两个同样的元素时清空,当窗口满且元素不一样时必然是第二个元素为要找的元素。
int find_singleton(int * arr, int n){
int i = 0;
while(i<n){
if(arr[i] == arr[i+1]){
i+=2;
}else{
return i+1;
}
}
只需遍历一次集合,复杂度O(n)
评分及理由
(1)得分及理由(满分3分)
学生给出的基本设计思想是维护滑动窗口并比较相邻元素,当遇到相邻元素不相等时返回第二个元素。虽然描述不够精确(例如"清空窗口"的表述不准确),但核心思想是通过比较相邻元素来定位唯一出现一次的元素,与标准答案的遍历偶数位置比较相邻元素的思想本质一致。因此不扣分,得3分。
(2)得分及理由(满分8分)
算法实现存在以下问题:
1. 代码逻辑错误:当相邻元素不相等时,返回的是索引i+1而不是元素值arr[i+1],这会导致返回错误结果(返回的是索引位置而非元素值)。
2. 边界情况处理不完整:如果唯一元素在最后一个位置,代码会访问越界(arr[i+1])且无法正确处理。
3. 缺少对最后一个元素的特殊处理。
基于上述逻辑错误,扣4分。代码结构基本正确,得4分。
(3)得分及理由(满分2分)
学生正确指出算法时间复杂度为O(n),分析正确,得2分。
题目总分:3+4+2=9分
登录后发布评论
暂无评论,来抢沙发