1029 Median

Posted on | Edited on | In , |

题目

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1 = { 11, 12, 13, 14 } is 12, and the median of S2 = { 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 S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their 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

想法

把两个数组分成两个部分，得到中位数

要考虑时间复杂度和空间复杂度

emm 先写一个普通的版本：

将两个数组存下来，然后从头开始遍历，两个指针比较着向前走，直到到达一半为止

实现如下：

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
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    vector<int> v2(N);
    for (int i = 0; i < N; i++) {
        cin >> v2[i];
    }
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    bool isV1 = !v1.empty();
    for (int i = 0; i <= half; i++) {
        if (p1 >= v1.size()) {
            isV1 = false;
            p2++;
        }
        else if (p2 >= v2.size()) {
            isV1 = true;
            p1++;
        }
        else {
            if (v1[p1] < v2[p2]) {
                p1++;
                isV1 = true;
            }
            else {
                isV1 = false;
                p2++;
            }
        }
    }
    cout << (isV1 ? v1[p1 - 1] : v2[p2 - 1]);
    return 0;
}

十分干净简单，但是最后一个测试点内存超限，而且，最后一个测试点10分，占了2/5的分数。

用的空间，也就存两个输入的数组，没有其它的空间了
这都内存超限的话，看来，不能把数据都存下来。

肯定要存输入的第一个数组。
对于第二个，必须边读入，边处理。

不存第二个，不就对了。

改进之后的版本：

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
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    int num1 = 0;
    int num2 = 0;
    bool isV1 = !v1.empty();
    queue<int> v2Buffer;
    for (int i = 0; i <= half; i++) {
        if (p1 >= M) {
            cin >> num2;
            p2++;
            isV1 = false;
        } else if (p2 >= N) {
            num1 = v1[p1];
            p1++;
            isV1 = true;
        } else {
            num1 = v1[p1];
            if (v2Buffer.empty()) {
                cin >> num2;
                v2Buffer.push(num2);
            } else {
                num2 = v2Buffer.front();
            }
            if (num1 < num2) {
                p1++;
                isV1 = true;
            } else {
                p2++;
                v2Buffer.pop();
                isV1 = false;
            }
        }
    }
    cout << (isV1 ? num1 : num2);
    return 0;
}

用了一个buffer来存比较之后，并没有用num2的情况下的num2.

内存超限没有了，不过还有个测试点没过，而且也是10分！！！
问题出在哪里呢？？？

不解，实在想不到..

看来，还是，考虑的不周到，没有玄学，只是问题不明显而已，buffer没有考虑全。

答案

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
//
// Created by Zhao Xiaodong on 2018/8/7.
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int M, N;
    cin >> M;
    vector<int> v1(M);
    for (int i = 0; i < M; i++) {
        cin >> v1[i];
    }
    cin >> N;
    int p1 = 0, p2 = 0;
    int sum = M + N;
    int half = (sum - 1) / 2;
    long num1 = 0;
    long num2 = 0;
    bool isV1 = !v1.empty();
    int v2Buffer;
    bool hasBuffer = false;
    for (int i = 0; i <= half; i++) {
        if (!hasBuffer) {
            cin >> num2;
            hasBuffer = true;
        }
        if (p1 >= M) {
            p2++;
            hasBuffer = false;
            isV1 = false;
        } else if (p2 >= N) {
            num1 = v1[p1];
            p1++;
            isV1 = true;
        } else {
            num1 = v1[p1];
            if (num1 < num2) {
                p1++;
                isV1 = true;
            } else {
                p2++;
                hasBuffer = false;
                isV1 = false;
            }
        }
    }
    cout << (isV1 ? num1 : num2);
    return 0;
}

感想

  1. 找问题，仔细找，用到每个“变”量，都要审核是否符合条件
  2. PAT更新后的分数好迷
  3. ios::sync_with_stdio(false)大法好，应该不用担心cin超时了hhh