文章
36
粉丝
0
获赞
2
访问
1.8k
评分及理由
(1)得分及理由(满分4分)
得0分。学生的设计思想是使用双指针遍历两个序列,每次比较当前指针所指元素,选择较小的作为候选值,并移动指针,直到计数达到L(即中位数的位置)。这种方法实际上是合并两个有序数组并找到第L小的元素,但题目要求的是两个序列的中位数,即合并后序列的中位数,而合并后序列长度为2L,中位数应为第L和L+1个元素的平均值(当L为偶数时)或第L+1个元素(当L为奇数时)?但题目定义中位数是第⌈L/2⌉个位置,但这里序列长度是2L,所以中位数应该是第L个元素(因为2L的升序序列中位数是第L个元素?实际上题目中S1和S2长度都是L,合并后长度为2L,中位数应为第L个元素(因为⌈2L/2⌉=L)。学生的方法在计数达到L时返回,确实可以找到第L小的元素,因此思路正确。但标准答案采用更高效的分治方法(O(log n)),而学生的方法是线性扫描(O(n)),虽然正确但不符合“时间尽可能高效”的要求(题目要求时间空间都尽可能高效,分治明显更优)。但题目要求“尽可能高效”,并未强制要求必须达到对数复杂度,且学生的思路正确,因此不扣分?但标准答案的算法是O(log n),而学生的是O(n),在效率上不足。然而题目要求的是“设计思想”,学生的方法基本正确,但未达到最优效率。根据打分要求“思路正确不扣分”,但这里效率较差,但题目并未明确必须最优,因此给部分分?但标准答案给的是满分思路,而学生的方法效率较低,但正确。考虑到题目要求“尽可能高效”,学生的线性方法虽然正确但不够高效,因此扣2分。得2分。
(2)得分及理由(满分9分)
得3分。学生的代码实现了双指针遍历,但在边界情况处理上有错误:
1. 当计数count达到L时返回ans,这可以正确得到第L小的元素(即中位数),但代码中未考虑一个序列提前遍历完的情况?实际上while条件保证了i和j都小于L,但当其中一个序列提前遍历完时,另一个序列剩余元素可能未被处理,但计数count可能还未达到L?例如,如果S1的所有元素都小于S2,那么i会先达到L,然后循环退出,但此时count可能小于L,导致无法返回结果(函数没有返回值,行为未定义)。这是一个逻辑错误,扣分。
2. 初始化ans为0xFFFFFFFF(即-1),但序列中可能包含负数?但题目中是升序序列,可能包含负数,但初始值设置可能不影响结果?因为...
登录后发布评论
暂无评论,来抢沙发