PAT-A 1029 Median (25)

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of $S_1$ = { 11, 12, 13, 14 } is 12, and the median of $S_2$ = { 9, 10, 15, 16, 17 } is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of $S_1$ and $S_2$ is 13.

Given two increasing sequences of integers, you are asked to find their median.

Problem: PAT-A 1029 Median

Input Specification

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤ 2 × $10^5$) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output Specification

For each test case you should output the median of the two given sequences in a line.

Sample Input

1
2

4 11 12 13 14
5 9 10 15 16 17

Sample Output

1

13

Analysis

  这题乍一看以为是水题（其实就是水题），看数蛮大的就想着用哈希表统计数字出现次数，然后从小到大累加数字出现次数直至到达中位数。写完交上去的瞬间以为过了，眼睛扫到最下面发现最后一个测试点运行超时…

  网上搜一圈题解看到很多写法，但无非都是 Two Pointers 的思想。和归并排序差不多，两个指针 i 和 j 分别指向两个序列 $S_1$ 和 $S_2$ 的头部，不断选择最小的元素以生成第三个序列 $S_3$ 也就是合并后的序列。为了节约空间和时间，只读入 $S_1$，$S_2$ 只记录指针当前指向得数，边读入边移动指针，找到中位数即可结束读入。根据题目要求我们不需要真的生成第三个序列，只找到中位数即可，也就是排除 ($N_1$ + $N_2$ - 1) / 2 个数，然后从两个指针指向的数中选择较小的一个输出。

  合并的序列 $S_3$ 中，可能出现 $S_1$ 所有数在中位数左边，或者 $S_2$ 所有数在中位数左边。因此在 $A_1$ 和 $A_2$ 的末尾添加无穷大，以结束该序列的搜索，具体见代码。

Code

  最开始的错误解法，哈希表统计数字。满心欢喜提交上去，结果有一个测试点显示超时，我枯了。

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

#include <bits/stdc++.h>
using namespace std;

map<int, int> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int mid = 0;
    for (int i = 0; i < 2; i++) {
       int N, num;
       cin >> N;
       mid += N;
       for (int j = 0; j < N; j++) {
            cin >> num;
            mp[num]++;
       }
    }
    mid = ceil(mid / 2.0);
    int cnt = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        if (cnt + it->second < mid) {
            cnt += it->second;
        } else {
            cout << it->first << endl;
            return 0;
        }
    }
}

  下面是 AC 代码。嫖了大佬思路，用 Two Pointers 思想的解法。

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N1, N2;
    cin >> N1;
    vector<int> S1(N1 + 1);
    for (int i = 0; i < N1; i++) {
        cin >> S1[i];
    }
    S1[N1] = INT_MAX;
    cin >> N2;
    int mid = (N1 + N2 - 1) / 2, S2, i = 0, j = 0, cnt = 0;
    cin >> S2;
    while (cnt++ < mid) {
        if (S1[i] < S2) {
            i++;
        } else {
            if (++j < N2) {
                cin >> S2;
            } else {
                S2 = INT_MAX;
            }
        }
    }
    cout << (S1[i] < S2 ? S1[i] : S2) << endl;
}

Tsukkomi

  想着好不容易逮到一道水题正好让我爽一下，唰唰唰写完交上去结果被测试点卡得怀疑人生。如果考试时候出了这么道题，那我可能要打出 GG 了。