PTA（顺序表）2-1 两个有序序列的中位数

2-1 两个有序序列的中位数

分数 6

作者 DS课程组

单位 浙江大学

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

1
2
3
5
1 3 5 7 9
2 3 4 5 6

输出样例1:

1
4

输入样例2:

1
2
3
6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1
1

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表，为其分配内存
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

// 归并L1和L2
sqList merge(sqList &L, sqList L1, sqList L2, int n) {
    int i = 0; // 用来遍历L1
    int j = 0; // 用来遍历L2
    int k = 0; // 用来遍历L
    while (i != n && j != n) { // 其中一个序列遍历完后结束循环
        if (L1.data[i] <= L2.data[j]) { // L1的元素小，先放入L
            L.data[k] = L1.data[i];
            L.length++;
            k++;
            i++;
        } else { // L2此时的元素小
            L.data[k] = L2.data[j];
            L.length++;
            k++;
            j++;
        }
    }
    while (j == n && i < n) { // 如果L2先遍历完，把L1剩余的放入
        L.data[k] = L1.data[i];
        L.length++;
        k++;
        i++;
    }
    while (i == n && j < n) { // 如果L1先遍历完，把L2剩余的放入
        L.data[k] = L2.data[j];
        L.length++;
        k++;
        j++;
    }
    return L;
}

int main() {
    int n;
    cin >> n; // 读取顺序表数据个数

    // 初始化两个顺序表
    sqList L1;
    sqList L2;
    initList(L1, n);
    initList(L2, n);

    // 给L1插入读取的数据
    for (int i = 0; i < n; ++i) {
        cin >> L1.data[i];
        L1.length++;
    }
    // 给L2插入读取的数据
    for (int i = 0; i < n; ++i) {
        cin >> L2.data[i];
        L2.length++;
    }

    // 求两个顺序表的并集，返回到新顺序表L中
    sqList L;
    initList(L, 2*n);
    merge(L,L1, L2, n);
    cout << L.data[(L.length-1) / 2];
}

注意事项：

  1. 核心方法：利用两个有序序列的特性，通过双指针技术归并（Merge）序列，无需完整排序即可找到中位数。
  2. 归并逻辑：
    • 用两个指针分别遍历两个序列，每次选择较小的元素放入结果序列。
    • 当一个序列遍历完后，直接将另一个序列的剩余元素追加到结果中。
  3. 中位数定位：两个长度为n的序列合并后总长度为2n，中位数是第n个元素（从 1 开始计数），对应下标n-1（从 0 开始计数）。

错误点总结

  1. 归并循环条件错误：
    • 初始循环条件i != n || j != n会导致其中一个序列遍历完后仍继续访问，引发数组越界（正确应为i < n && j < n，仅当两个序列都未遍历完时循环）。
  2. 中位数计算错误：
    • 错误使用(L.length+1)/2计算下标，忽略了题目中 “第⌊(N+1)/2⌋个数” 的定义（对于2n长度的序列，中位数下标应为n-1）。

通过修正这些问题，代码能够正确利用归并思想高效求解中位数，时间复杂度为O(n)，空间复杂度为O(n)，符合题目要求。