筆試時(shí)間：2025年03月30日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：提取中位數(shù)

給出一個(gè)長(zhǎng)度為 n 的序列 a1,a2,a3?a**n，請(qǐng)你按照以下規(guī)則輸出序列的中位數(shù)：如果序列的大小為奇數(shù)，則中位數(shù)是按照升序排序后中間的數(shù)字。如果序列的大小為偶數(shù)：按照升序排序后，中間的兩個(gè)數(shù)字 x=y時(shí)，輸出任意一個(gè)即可；按照升序排序后，中間的兩個(gè)數(shù)字 x\=y時(shí)，輸出 min(x,y)，即 x和 y中較小的那個(gè)數(shù)。當(dāng)輸出中位數(shù) mid_x時(shí)，該中位數(shù) mid_x從序列 a中消失，再輸出消失后的序列 a′ 中位數(shù)。重復(fù)上述步驟，直至全部將序列 a全部輸出。

輸入描述

第一行輸入一個(gè)正整數(shù) n(1≤n≤105) 代表序列長(zhǎng)度。

第二行輸入 n個(gè)正整數(shù) a1,a2,?,a^n (1≤a^i≤109) 代表序列元素。

輸出描述

在一行上輸出 n個(gè)整數(shù)代表依次提取出的中位數(shù)。

樣例輸入

4

1 9 8 5

樣例輸出

5 8 1 9

參考題解

要?jiǎng)討B(tài)提取中位數(shù)并維護(hù)剩余序列的中位數(shù)。核心思路是預(yù)先排序數(shù)組，然后通過雙指針模擬動(dòng)態(tài)刪除中位數(shù)的過程。排序預(yù)處理首先對(duì)數(shù)組進(jìn)行排序，便于后續(xù)快速定位中位數(shù)。奇偶分類處理奇數(shù)長(zhǎng)度：直接取中間元素作為第一個(gè)中位數(shù)，剩余元素分為左右兩部分，用雙指針交替取元素。偶數(shù)長(zhǎng)度：取中間左側(cè)較小元素作為第一個(gè)中位數(shù)，隨后左右指針分別向兩側(cè)擴(kuò)展，交替取元素。雙指針模擬刪除利用左右指針動(dòng)態(tài)維護(hù)剩余元素的邊界，每次取完一個(gè)中位數(shù)后，指針向兩側(cè)移動(dòng)以模擬刪除操作。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測(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：[此代碼未進(jìn)行大量數(shù)據(jù)的測(cè)試，僅供參考]

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：[此代碼未進(jìn)行大量數(shù)據(jù)的測(cè)試，僅供參考]

def extract_medi