笔试时间：2025年03月30日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：提取中位数

给出一个长度为 n 的序列 a1,a2,a3⋯a**n，请你按照以下规则输出序列的中位数：如果序列的大小为奇数，则中位数是按照升序排序后中间的数字。如果序列的大小为偶数：按照升序排序后，中间的两个数字 x=y时，输出任意一个即可；按照升序排序后，中间的两个数字 x\=y时，输出 min(x,y)，即 x和 y中较小的那个数。当输出中位数 mid_x时，该中位数 mid_x从序列 a中消失，再输出消失后的序列 a′ 中位数。重复上述步骤，直至全部将序列 a全部输出。

输入描述

第一行输入一个正整数 n(1≤n≤105) 代表序列长度。

第二行输入 n个正整数 a1,a2,⋯,a^n (1≤a^i≤109) 代表序列元素。

输出描述

在一行上输出 n个整数代表依次提取出的中位数。

样例输入

4

1 9 8 5

样例输出

5 8 1 9

参考题解

要动态提取中位数并维护剩余序列的中位数。核心思路是预先排序数组，然后通过双指针模拟动态删除中位数的过程。排序预处理首先对数组进行排序，便于后续快速定位中位数。奇偶分类处理奇数长度：直接取中间元素作为第一个中位数，剩余元素分为左右两部分，用双指针交替取元素。偶数长度：取中间左侧较小元素作为第一个中位数，随后左右指针分别向两侧扩展，交替取元素。双指针模拟删除利用左右指针动态维护剩余元素的边界，每次取完一个中位数后，指针向两侧移动以模拟删除操作。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void extract_medians() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end());
    vector<int> result;

    if (n % 2 == 1) {  // Odd length
        int mid = n / 2;
        result.push_back(nums[mid]);
        int left = mid - 1;
        int right = mid + 1;
        for (int i = 0; i < (n - 1) / 2; ++i) {
            result.push_back(nums[left]);
            left--;
            result.push_back(nums[right]);
            right++;
        }
    } else {  // Even length
        int left = (n / 2) - 1;
        int right = n / 2;
        for (int i = 0; i < n / 2; ++i) {
            result.push_back(nums[left]);
            left--;
            result.push_back(nums[right]);
            right++;
        }
    }

    for (int i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }
    cout << endl;
}

int main() {
    extract_medians();
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void extractMedians() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        
        for (int i = 0; i < n; ++i) {
            nums[i] = scanner.nextInt();
        }

        Arrays.sort(nums);
        List<Integer> result = new ArrayList<>();

        if (n % 2 == 1) {  // Odd length
            int mid = n / 2;
            result.add(nums[mid]);
            int left = mid - 1;
            int right = mid + 1;
            for (int i = 0; i < (n - 1) / 2; ++i) {
                result.add(nums[left]);
                left--;
                result.add(nums[right]);
                right++;
            }
        } else {  // Even length
            int left = (n / 2) - 1;
            int right = n / 2;
            for (int i = 0; i < n / 2; ++i) {
                result.add(nums[left]);
                left--;
                result.add(nums[right]);
                right++;
            }
        }

        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        extractMedians();
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def extract_medi