58同城笔试 58同城笔试题 1018

笔试时间: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, 

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

2024 BAT笔试合集 文章被收录于专栏

持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
07-02 13:50
闽江学院 Java
点赞 评论 收藏
分享
缒梦&独舞:这家公司是这样的,去年给我实习offer了,不过也是面着玩儿的,他周六还要去做公益志愿活动
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务