笔试时间：2024年10月18 秋招

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

第一题

题目

平均值是统计学中常用的指标之一，可以表示—组数据的中心趋势。然而，平均值容易受到极端值(异常值或离群点）的影响，导致结果失真。在数据集存在极端值或分布不均时，可以结合中位数等其他统计指标进行综合分析。中位数是指在一组有序数据中处于中间位置的数值，它将数据集分为两个部分，使得其中—半数据的数值小于等于它，另一半数据的数值大于等于它。对于奇数个数据:如果数据集的数量是奇数，则中位数是排序后处于中间位置的那个数。例如，对于数据集3,5,7，排序后中位数为5。对于偶数个数据:如果数据集的数量是偶数，则中位数是排序后位于中间的两个数中较小的那个数。例如，对于数据集2,4,6,8，排序后中位数为4。假设现在有两个长度均为N且元素不重复的有序数组(从小到大) array1和array2，请计算这两个有序数组合并后的中位数。要求:时间复杂度为O(logN)，额外的空间复杂度O(1)，不能使用sort函数。

样例输入一

[1.00000, 3.00000, 7.00000],[2.0000, 5.00000, 10.00000]

样例输出一

3.00000

样例输入二

[2.00000, 6.00000],[4.50000, 8.00000]

样例输出二

4.50000

参考题解

通过二分查找在两个有序数组中找到一个合适的分割点，使得合并后的左右两部分满足左边最大值小于等于右边最小值，从而确定合并后数组的中位数。

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

#include <iostream>
#include <vector>
#include <limits>

class Solution {
public:
    float find_median(const std::vector<float>& array1, const std::vector<float>& array2) {
        int N = array1.size();
        int low = 0, high = N;

        while (low <= high) {
            int i = (low + high) / 2;
            int j = N - i;

            float maxLeft1 = (i == 0) ? -std::numeric_limits<float>::infinity() : array1[i - 1];
            float minRight1 = (i == N) ? std::numeric_limits<float>::infinity() : array1[i];

            float maxLeft2 = (j == 0) ? -std::numeric_limits<float>::infinity() : array2[j - 1];
            float minRight2 = (j == N) ? std::numeric_limits<float>::infinity() : array2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                return std::max(maxLeft1, maxLeft2);
            } else if (maxLeft1 > minRight2) {
                high = i - 1;
            } else {
                low = i + 1;
            }
        }
        return 0.0f;
    }
};

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

import java.util.*;
public class Solution {
    public float find_median (float[] array1, float[] array2) {
        int N = array1.length;
        int low = 0;
        int high = N;

        while (low <= high) {
            int i = (low + high) / 2;
            int j = N - i;

            float maxLeft1 = (i == 0) ? Float.NEGATIVE_INFINITY : array1[i - 1];
            float minRight1 = (i == N) ? Float.POSITIVE_INFINITY : array1[i];

            float maxLeft2 = (j == 0) ? Float.NEGATIVE_INFINITY : array2[j - 1];
            float minRight2 = (j == N) ? Float.POSITIVE_INFINITY : array2[j];

            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                return Math.max(maxLeft1, maxLeft2);
            } else if (maxLeft1 > minRight2) {
                high = i - 1;
            } else {
                low = i + 1;
            }
        }
        return 0.0f;
    }
}

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

import math

class Solution:
    def find_median(self, array1, array2):
        N = len(array1)
        low, high = 0,