(1)设置变量l计算A，B的长度，设置变量k初始为0和i，j变量初始为0表示序列A和序列B指向数据，每次比较i，j若A[i]<B[j]则i++反之j++，然后k++,当k等于L/2时找到2个序列的中位数。
(2)
int mid(vector<int>&arr1,vector<int>&arr2){
int l=arr1.size();
int k=0,i=0,j=0;
while(k<l){
if(arr1[i]>arr2[j]){
j++;
k++;
}else{
i++;
k++;
}
}
return max(arr1[i],arr2[j]);
}
(3)时间复杂度O(n),空间复杂度O(1)
评分及理由
（1）得分及理由（满分4分）
得分：0分
理由：学生的设计思想是使用双指针遍历两个序列，通过比较和移动指针来寻找中位数。但这种方法实际上是在模拟归并排序的合并过程，试图找到第L小的元素（因为总长度为2L，中位数是第L小的元素）。然而，学生的思路描述不清晰，且未正确理解题目要求的中位数定义（两个序列的中位数是含所有元素的升序序列的中位数，即第L小的元素）。标准答案采用分治策略，每次比较两个序列的中位数并舍弃一半，效率更高（O(log n)）。学生的思路虽然可行，但时间复杂度为O(n)，不符合“时间尽可能高效”的要求，且未正确描述如何找到中位数（例如，当k达到L时，返回的max(arr1[i], arr2[j])并不一定是中位数，因为指针移动可能越界或逻辑错误）。因此，本部分得0分。
（2）得分及理由（满分9分）
得分：0分
理由：学生的代码存在严重逻辑错误：
1. 代码中while循环条件为k < l，但l是单个序列的长度（假设为L），而总元素数为2L，中位数应是第L小的元素（从1计数），但循环中k从0增加到L-1（共L次移动），最终i和j指向的位置并不对应第L小的元素。
2. 在循环中，每次比较arr1[i]和arr2[j]，移动较小值的指针，但当k达到L时，循环结束，此时应取min(arr1[i], arr2[j])（因为最后一步移动后，可能有一个指针指向的元素较小），但学生返回max(arr1[i], arr2[j])，这显然是错误的...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发