文章
238
粉丝
0
获赞
3
访问
33.1k
评分及理由
(1)得分及理由(满分4分)
学生答案的基本设计思想是使用哈希表统计元素出现次数,然后遍历哈希表检查是否存在出现次数超过n/2的元素。这种方法虽然正确,但不符合题目要求的“尽可能高效的算法”中的“高效”指时间复杂度O(n)和空间复杂度O(1)的优化目标(标准答案使用摩尔投票法,空间复杂度为O(1))。但题目并未强制要求空间复杂度为O(1),且哈希表方法的时间复杂度为O(n),也是正确的解法。因此,思路正确,不扣分。得4分。
(2)得分及理由(满分7分)
学生代码实现了哈希表方法,逻辑正确:初始化哈希表、统计次数、检查主元素。但存在以下问题:
1. 代码中使用了变长数组(int hash[n]),在C99标准中合法,但部分环境可能不支持。不过题目允许C/C++/Java,且学生明确使用C语言,因此不扣分。
2. 变量m定义为n/2,但整数除法会向下取整,而主元素要求m>n/2(严格大于)。例如n为偶数时,n/2是整数,但主元素需要至少n/2+1次出现。代码中条件为hash[i] > m,正确(因为m=n/2是整数,若hash[i]=n/2+1则大于m)。但需注意n为奇数时n/2向下取整,例如n=5时m=2,主元素需要至少3次,条件hash[i]>2正确。因此逻辑无误。
3. 代码未处理n=0的情况,但题目未明确要求边界,因此不扣分。
整体实现正确,但空间复杂度为O(n),不符合“尽可能高效”中的空间优化意图。但题目未明确要求空间复杂度O(1),且算法正确,因此扣1分(空间效率不足)。得6分。
(3)得分及理由(满分2分)
学生正确分析了时间复杂度O(n)和空间复杂度O(n),与实现一致。得2分。
题目总分:4+6+2=12分
登录后发布评论
暂无评论,来抢沙发