文章
54
粉丝
21
获赞
0
访问
4.0k
(1)A和B等长,那么两个序列的中位数即A和B中第n大的元素,令i=0,j=0,循环遍历A和B,若A[i]<B[j],则i++,否则j++,直到找到第n个元素为止。
(2)
(3)循环了L次,所以时间复杂度为O(L);并没有建立数组,所以空间复杂度为O(1)。
评分及理由
(1)得分及理由(满分4分)
得0分。学生的基本设计思想是使用双指针遍历两个数组,通过比较A[i]和B[j]的大小来移动指针,直到找到第n个元素。这种方法的时间复杂度为O(n),虽然正确但不符合题目要求的"尽可能高效"(标准答案采用二分法达到O(log₂n))。由于题目明确要求时间和空间都尽可能高效,而学生的方法在时间效率上明显低于最优解,因此不能得分。
(2)得分及理由(满分9分)
得3分。代码实现存在多处问题:
1. 函数参数不完整,缺少序列长度参数
2. 变量L未定义
3. 逻辑错误:当n+1==L时返回的是A[i]或B[j],但此时i或j已经自增,实际返回的是下一个元素
4. 边界情况处理不当,可能导致数组越界
5. 代码无法正确处理所有情况
考虑到代码基本实现了双指针遍历的思路,但存在严重逻辑错误,给予3分。
(3)得分及理由(满分2分)
得1分。时间复杂度分析正确为O(L),空间复杂度分析正确为O(1)。但由于时间复杂度分析中使用了L而不是n,且未说明L与n的关系(题目中序列长度为n),扣1分。
题目总分:0+3+1=4分
登录后发布评论
暂无评论,来抢沙发