[PAT-A] 1029 Median

Java

package PAT_A1029_Median;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        // 序列1
        String[] line = reader.readLine().split(" ");
        int N1 = Integer.parseInt(line[0]);
        long[] num1 = new long[N1 + 1];
        for (int i = 0; i < N1; i++)
            num1[i] = Long.parseLong(line[i + 1]);

        // 序列2
        line = reader.readLine().split(" ");
        int N2 = Integer.parseInt(line[0]);
        long[] num2 = new long[N2 + 1];
        for (int i = 0; i < N2; i++)
            num2[i] = Long.parseLong(line[i + 1]);

        // 序列最后一个元素置INF
        num1[N1] = num2[N2] = Long.MAX_VALUE;

        int cnt = 0, i = 0, j = 0;
        while (cnt < (N1 + N2 - 1) / 2) {
            if (num1[i] < num2[j]) {
                i++;
            } else {
                j++;
            }
            cnt++;
        }

        // 输出两个序列当前位置较小的元素
        System.out.println(Math.min(num1[i], num2[j]));
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m;
int a[N], b[N], c[N * 2];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) scanf("%d", &b[i]);

    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];

    if (k % 2 == 1) printf("%d\n", c[k / 2]);
    else printf("%d\n", c[k / 2 - 1]);

    return 0;
}