笔试时间：2024年07月20日 提前批

历史笔试传送门：2023秋招笔试合集

第一题

题目

给出一个长度为n的序列a1,a2,a3,...an，请你按照以下规则输出序列的中位数：

1.如果序列的大小为奇数，则中位数是按照升序排序后中间的数字。

2.如果序列的大小为偶数:

• 按照升序排序后，中间的两个数字x=y时输出任意一个即可
• 按照升序排序后，中间的两个数字x!=y时输出min(x,y)，即 x 和 y 中较小的那个数。当输出中位数 mid时，该中位数 mid从序列 a中消失，再输出消失后的序列 a’ 的中位数。

重复上述步骤，直至全部将序列 a全部输出。

输入描述

第一行输入一个正整数 n (1<= n <= 10^5)代表序列长度。

第二行输入n 个正整数代表序列元素a1,a2,a3,...an 代表序列元素。

输出描述

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

样例输入一

5

4 1 8 9 5

样例输出一

5 8 1 9

样例输入二

6

6 6 6 6 6 6

样例输出二

6 6 6 6 6 6

参考题解

堆排序，使用一个有序集合维护，每次取出 s[n/2]后，删除这个数即可。

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

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class MedianFinder {
private:
    priority_queue<int> large; // 大根堆
    priority_queue<int, vector<int>, greater<int>> small; // 小根堆

public:
    MedianFinder() {}

    void addNum(int num) {
        large.push(num);
        small.push(large.top());
        large.pop();
        if (large.size() < small.size()) {
            large.push(small.top());
            small.pop();
        }
    }

    double findMedian() {
        double x = 0;
        if (small.size() < large.size()) {
            x = large.top();
            large.pop();
        } else if (small.size() == large.size()) {
            x = large.top();
            large.pop();
        }

        if (small.size() > large.size()) {
            large.push(small.top());
            small.pop();
        }

        return x;
    }
};

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

    MedianFinder mf;
    for (int i = 0; i < n; ++i) {
        mf.addNum(a[i]);
    }
    for (int i = 0; i < n; ++i) {
        cout << mf.findMedian() << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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

import java.util.PriorityQueue;
import java.util.Scanner;

public class MedianFinder {
    private PriorityQueue<Integer> small; // 小根堆
    private PriorityQueue<Integer> large; // 大根堆

    public MedianFinder() {
        small = new PriorityQueue<>(); // 小根堆
        large = new PriorityQueue<>((a, b) -> b - a); // 大根堆，使用 lambda 表达式实现大根堆
    }

    public void addNum(int num) {
        large.offer(num);
        small.offer(large.poll());
        if (large.size() < small.size()) {
            large.offer(small.poll());
        }
    }

    public double findMedian() {
        double x = 0;
        if (small.size() < large.size()) {
            x = large.poll();
        } else if (small.size() == large.size()) {
            x = large.poll();
        }

        if (small.size() > large.size()) {
            large.offer(small.poll());
        }

        return x;
    }

    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = sc.nextInt();
        }

        MedianFinder mf = new MedianFinder();
        for (int x : a) {
            mf.addNum(x);
        }
        for (int i = 0; i < n; ++i) {
            System.out.print(mf.findMedian() + " ");
        }
        System.out.println();
    }

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

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

import heapq
import sys
input = lambda: sys.stdin.readline().rstrip()
sint = lambda: int(input())
ints = lambda: list(map(int, input().split()))

class MedianFinder:
    def __init__(self):
        self.small = [] # 小根堆
        self.large = [] # 大根堆

    def addNum(self, num: int) -> None:
        heapq.heappush(self.large, -num)
        heapq.heappush(self.small, -heapq.heappop(self.large))
        if len(self.large) < len(self.small):
            heapq.heappush(self.large, -heapq.heappop(self.small))

    def findMedian(self) -> float:
        x = 0
        if len(self.small) < len(self.large):
            x = -self.large[0]
            heapq.heappop(self.large)
        elif len(self.small) == len(self.large):
            x = -self.large[0]
            heapq.heappop(self.large)

        if len(self.small) > len(self.large):
            heapq