V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Daredevil0086
V2EX  ›  程序员

面试题:如何 O(n) 的复杂度内筛选 60 亿人的身高

  •  
  •   Daredevil0086 · 304 天前 · 9538 次点击
    这是一个创建于 304 天前的主题,其中的信息可能已经有所发展或是发生改变。

    完整的题目差不多是这样的:

    现在有一个文件 a.txt ,其中放的内容就是 60 亿人的身高,每个身高数据都保证是以.0 或者.5 结尾的(比如说 180.0 ,175.5 );现在请筛选出其中前 1000 高的数据;

    要求时间复杂度是 o(n);

    面试官说这玩意不是一个单纯的算法,身高数据可以做点文章……但到最后还是没想出来………………有没有高智商 V 友可以解答一下

    第 1 条附言  ·  304 天前
    感谢各位高智商 V 友的各种回答和意见,感觉基本确定了答案就是 1L 和 6L 的方案就是面试官想要的~~~

    总之,千言万语汇成一句话:

    家人们,爱你啾咪❤,mua~~
    87 条回复    2023-05-30 19:05:02 +08:00
    fengjianxinghun
        1
    fengjianxinghun  
       304 天前   ❤️ 5
    人类的身高是有上下限的,正确点说就是 0.5-3 米之间,而且他保证了是.0/.5 结尾,就减少到一个更小的数值集合,这样想你是不是就懂了?
    lolizeppelin
        2
    lolizeppelin  
       304 天前   ❤️ 1
    遍历的时候超过 2 米的.....或者低一点 1.95
    iamzuoxinyu
        3
    iamzuoxinyu  
       304 天前
    桶排序
    Nugine0
        4
    Nugine0  
       304 天前 via Android   ❤️ 3
    基数排序
    Daredevil0086
        5
    Daredevil0086  
    OP
       304 天前
    @iamzuoxinyu 桶排序最差能到 O(n^2)吧,不在 O(n)内
    leogm9408leo
        6
    leogm9408leo  
       304 天前   ❤️ 66
    数据是以.0 或者.5 结尾,意味着这是个有范围的离散数据而不是连续数据。假设人类的身高区间是 10 厘米-250 厘米,间距 0.5 厘米,其实也就( 250-10 )*2=480 个。作 480 个数据桶,遍历一遍就可以把 60 亿数据都放到这 480 个数据桶里,然后取不为空的最大身高值的桶里的数据即可
    devfeng
        7
    devfeng  
       304 天前
    https://leetcode.cn/problems/kth-largest-element-in-an-array/ 第 k 个最大元素,思路是一样的
    edward1987
        8
    edward1987  
       304 天前   ❤️ 4
    前 1000 高的,又不是所有都排序,用一个数组存当前最高的 1000 个,遍历一遍,遇到更高的就替换数组内容就好了啊。复杂度就是 0(n)
    Daredevil0086
        9
    Daredevil0086  
    OP
       304 天前
    @fengjianxinghun 额,即使是不看结尾小数,好像稳定在 O(n)内的排序算法也没有吧
    githmb
        10
    githmb  
       304 天前
    一个容量为 1000 的向量,60 亿数据依次往里面塞,每塞一次做个排序
    Daredevil0086
        11
    Daredevil0086  
    OP
       304 天前
    @devfeng 哦哦哦哦,那我算答对了?我用的是快排那个…………………………但是还是没太理解怎么用身高这点来做优化
    insanny
        12
    insanny  
       304 天前
    同意 6 楼的思路
    raycool
        13
    raycool  
       304 天前
    堆排序
    sun1991
        14
    sun1991  
       304 天前
    开一个 HashMap, 把可能的身高数据以 key 的形式预先插入. 然后遍历集合, 插入 HashMap. 最后以身高为 key, 从高到底, 从 HashMap 拿数据, 凑满 1000 即可.
    FACEB00K
        15
    FACEB00K  
       304 天前
    不考虑身高数据,构建 size 为 1000 的最小堆;
    如果考虑升高数据,用一个数组统计身高就能解决吧,数组下标和身高有映射关系,而且身高范围是固定的;最后逆序遍历数组
    Daredevil0086
        16
    Daredevil0086  
    OP
       304 天前
    @edward1987 那是平均复杂度吧,面试官这么说的……
    coyoteer
        17
    coyoteer  
       304 天前
    计数排序?
    picone
        18
    picone  
       304 天前
    @FACEB00K 用了堆就不是 O(n) 了
    codingbody
        19
    codingbody  
       304 天前
    @edward1987 #8
    @raycool #13 这是 O(nlogk) 吧
    Daredevil0086
        20
    Daredevil0086  
    OP
       304 天前
    兄弟们,面试官好像想考察的是怎么用身高做文章,我最终交上去的答案是 7 楼贴的 leetcode 题目的快排版本答案;

    感觉这题,好像跟算法没关系~~~~属于动脑子的那种
    UnknoownUser
        21
    UnknoownUser  
       304 天前
    // (3-1.9)/0.05=22
    int counter[22];
    UnknoownUser
        22
    UnknoownUser  
       304 天前
    @UnknoownUser 时间复杂度为 O(n)就只能每个数据都访问一次咯,大致猜测一下前 1000 高的人类应该在 1.9-3.0m 之间,所以遍历一次用计数器把它们都记录下来
    xuanbg
        23
    xuanbg  
       304 天前
    6 楼正解
    FACEB00K
        24
    FACEB00K  
       304 天前
    @codingbody
    @picone k 不是一个常数吗,这里是 1000
    tuxz
        25
    tuxz  
       304 天前
    线性直方图
    icyalala
        26
    icyalala  
       304 天前
    "前 1000 高的数据" 要去重吗?
    picone
        27
    picone  
       304 天前
    @FACEB00K #24 其实是 n 次 大小为 1000 的堆插入,应该是 n * log2(1000)
    lymanlai
        28
    lymanlai  
       304 天前
    感觉在写回字的几种写法。。
    mxT52CRuqR6o5
        29
    mxT52CRuqR6o5  
       304 天前
    我很怀疑面试官是不是自以为是的认为桶排序算是一种优化
    IwfWcf
        30
    IwfWcf  
       304 天前
    面试官都提示得那么明显了,就是在提示桶的数量很少啊……
    FACEB00K
        31
    FACEB00K  
       304 天前
    @picone 一般是像你这么算的,每次都是和堆顶比较,比堆顶大的才删除堆顶,再插入;如果比堆顶小,直接就 pass 了,算法复杂度就是 O(nlogk);但是身高应该是符合正态分布的,前 1000 名身高可能只占百分之零点零几,甚至更少,60 亿数据中,基本上没多少次插入
    tyler1128
        32
    tyler1128  
       304 天前   ❤️ 1
    受 6 楼启发,480 个桶,先取 1000 个放入各自的桶内,然后淘汰掉数量不为 0 的最小的桶后面的所有桶,初始化一个计数器,初始值为最小的桶内令牌的数量。后面再次取数时,如果小于最小的桶,直接丢弃(节省哈希时间),如果这个数是此时场上最小的桶,则计数器加 1 ,如果不是最小的桶,计数器-1 ,当计数器为 0 时,丢弃最小的桶,重新排序找到新的最小的桶,计数器设置为新的最小的桶内令牌数量。重复该操作,直到遍历完 60 亿数,此时剩下的就是最大的 1000 个(数量可能会超过 1000 ,因为最小的桶可能有很多相同的值)。
    picone
        33
    picone  
       304 天前
    @FACEB00K #31 题目没有这个假设,这样不太合适。 即使有这个假设,按照二八分布,顶多也只能是 0.8n + 0.2 * n * log2(1000),也不完全是 O(n)
    HashV2
        34
    HashV2  
       304 天前
    嗯 应该就是先考察一个 topk 的算法问题,然后主要让你谈这个数据可以干嘛

    60 亿是一个全球人数级别的数据,但是我也想不出这个数据到底可以做啥文章😂
    UIXX
        35
    UIXX  
       304 天前
    也不考虑 O(n),我们的期望是 [一轮遍历+尽可能少的空间] 达到筛选目的。

    在现实中处理此类问题需要数据清洗并建模,简单地,我们需要预估身高分布,比如是全随机分布还是正态分布?

    无论是哪一种,我们都能估算出一个合适的身高范围,如果用桶,这个范围会使桶的数量大大减少。
    wanguorui123
        36
    wanguorui123  
       304 天前
    分别创建:List ,最大变量 A ,最小变量 B ,遍历 txt 数据时每次和最大变量 A 和最小变量 B 对比,将最大数据计入即可,然后加入 List ,让 List 始终保持 1000 个以内即可,遍历完成后对 List 快速排序既可以,非常简答
    akira
        37
    akira  
       304 天前
    这样 身高数据 是有限的啊。。统计出 每个高度的人数,然后从上往下拿够 1000 个
    pkoukk
        38
    pkoukk  
       304 天前
    @wanguorui123
    不行的。假如数据集中的第一个值是 max,第二个值是 min ,那 list 跑到最后只有两个元素。
    e7
        39
    e7  
       304 天前
    1L 就已经给出标准答案了,任何带比较的都超过 O(n)了,btw:面试官挺无聊的
    mmuggle
        40
    mmuggle  
       304 天前
    2000cm 不够高是吧?直接 O(1) 🤣
    darkengine
        41
    darkengine  
       304 天前
    确实是基数排序,只不过基用的是人类的身高,例如 355.0, 354.5 。
    8355
        42
    8355  
       304 天前
    1 楼说的是对的,这是常识问题加基本方案解决.
    其他说 60 亿次遍历或者比较的方案最大的问题就是存储 60 亿的问题必然是不符合出题者的意图的.
    我猜应该就是要问布隆过滤器吧.
    cclin
        43
    cclin  
       304 天前
    打开算法导论,翻到 112 页,得到一个最差时间复杂度 O(n) 的算法
    顺便 60 亿个数字在现在的硬件上不算一个很大的规模
    鉴定为题出得不行
    iOCZ
        44
    iOCZ  
       304 天前
    topK 算法挺常见的。用优先级队列构造 1000 个容量的小根堆,比堆顶小的舍弃,比堆顶大的进入。这个复杂度是 O(n*log2n)。要达到 o(n)的话,得使用空间复杂度更高的,类似计数排序。因为身高肯定是一个有限的数据点集,可以简单通过计数来实现获取前 1000 的数据。
    yzbythesea
        45
    yzbythesea  
       304 天前 via iPhone
    经典堆排序问题

    时间复杂度说 O(nlogk) 是错误的、说明不理解复杂度一说。n 和 k 不在一个量级可把 logk 视为常量。
    XiLingHost
        46
    XiLingHost  
       304 天前
    这不是很典型的计数排序场景吗......
    NoOneNoBody
        47
    NoOneNoBody  
       304 天前
    身高符合正态分布,六百万分之一只考虑>2m 就够了
    算法我是文盲,pass
    ytmsdy
        48
    ytmsdy  
       304 天前
    o(n)的复杂度应该不难吧。只需要前 1000 ,又不用全部数据排序。
    搞一个长度为 1000 的数组,搞一个插入排序,如果值大于 1000 中的最小值,那就插入,并把最后那个元素给删掉。
    其实也就是 1000*o(n)的复杂度,也就 O(n)的复杂度
    iOCZ
        49
    iOCZ  
       304 天前
    @yzbythesea 你说得对,我这个复杂度写错了。
    geelaw
        50
    geelaw  
       304 天前 via iPhone   ❤️ 5
    O(n) 和 o(n) 是不同的意思,后者是前者的真子集。更不能写成 0(n),最后这个东西只能被理解为零乘 n ,也就是 0 。

    另外问题的表述不清楚:n 是什么?

    合理的表述如下:文件里有 n 个人的身高(厘米)且每个数据都是 整数.0 或者 整数.5 ,求最高的 1000 个人的身高。要求算法是 O(n) 时间的。

    60 亿和 1000 都是常数,原来表述下的问题可以在 O(1) 时间内解决。
    ershierdu
        51
    ershierdu  
       304 天前
    @geelaw
    想起了去年找实习的面试,一道字符串相关的题,大意是给定一个字符串,找出其中第一个“只出现了一次的字符”的下标。我用 HashMap 做的,在已经明确字符串只包含英文字母的前提下,面试官非说最坏时间复杂度是 O(nlog n),因为底层的红黑树最坏就是 O(n logn)…
    ershierdu
        52
    ershierdu  
       304 天前
    @ershierdu
    typo:底层红黑树最坏是 O(log n)
    wudicgi
        53
    wudicgi  
       304 天前
    用 hashtable, key 为身高, value 为该身高出现的次数
    最后取出 hashtable 的 key, 按从大到小的顺序排序,再逐个看 value, 输出 key 的值直到 value 加起来 >= 1000
    这样可行不?
    sylxjtu
        54
    sylxjtu  
       304 天前
    可以参考《编程珠玑》第一章,讲得非常清楚
    tiandao84
        55
    tiandao84  
       304 天前 via iPhone
    好久没做题我也知道😯遍历一遍构建大顶堆,复杂度 O(n+LogN)
    zhy0216
        56
    zhy0216  
       304 天前   ❤️ 1
    @tiandao84 对的
    而且不需要“每个身高数据都保证是以.0 或者.5 结尾的”的条件
    20015jjw
        57
    20015jjw  
       304 天前 via iPhone
    bucket sort 例题啊 cs61b…
    veike
        58
    veike  
       304 天前
    @leogm9408leo 兄弟有博客吗,关注一波
    Knuth
        59
    Knuth  
       304 天前
    @20015jjw 果然湾区
    xxfye
        60
    xxfye  
       304 天前
    首先,1k 的排序可以视作常数,剩下的看你们发挥了。
    Badlink
        61
    Badlink  
       304 天前
    60 亿,假设每个身高浮点数表示的话是 8 字节,大概 5 * 10^10 B = 50G 。如果内存放不下的话就放 50 个文件,每次对一个文件桶排序,取前 1000 个,最后对这 50 个文件共 50000 个数再桶排序一次
    oamu
        62
    oamu  
       304 天前 via iPhone
    @picone 时间复杂度是对于输入来说的,在这个问题里,输入是 60 亿的身高数据,用一个大小为 1000 的堆进行排序取前 1000 大的数据,这个 1000 就是个常数,总的时间复杂度就是 O(n)。
    tyrantZhao
        63
    tyrantZhao  
       304 天前
    位图
    k9982874
        64
    k9982874  
       303 天前 via Android
    这题内存没限制的情况下不是 for loop 一遍就出结果了吗
    mingl0280
        65
    mingl0280  
       303 天前 via Android
    先来一个长度 480 的 int 数组,然后身高*2%480 到桶里,最后从前往后输出不为零的项就完事了
    mingl0280
        66
    mingl0280  
       303 天前 via Android
    如果要剪枝还可以直接滤掉身高小于两米的……
    hxysnail
        67
    hxysnail  
       303 天前
    用一个规模为 1000 的最小堆,然后遍历数据,如果比堆顶大,就替换堆顶,再调整一下堆结构。遍历完好,堆里面的数据就是前 1000 。

    由于 1000 是固定的,每次维护最小堆的时间可以认为是一个常量 k ,这样一来,时间复杂度为 O(kN),等价与 O(N)。
    这个方法适用于任何数据,从 N 个数据中取最大或最小的 n 个,只要 n 远小于 N 就行。
    bianhui
        68
    bianhui  
       303 天前
    60 亿人任何一个人的身高都不止一个人,只需找到最高的人,然后输出一千次就行了
    WngShhng
        69
    WngShhng  
       303 天前
    不是吧,如果要在更小的范围内搜索,前提是数据是有序的,如果数据经过排序,复杂度就达不到 O(n) 的要求。不考虑内存的话,遍历一遍,将 top 高的数据记录在一个列表里,同时记录这个列表的最小值,然后如果遇到高于这个最小值的或者列表还没满,这个时候把数据塞到列表里,同时更新列表的最小值,即可。这样对于列表不需要进行额外的排序浪费时间复杂度,这样才可以达到 O(n) 的要求。如果考虑实际情况,这个问题难度在于如何分块读取数据,以保证读取数据到内存之后,内存不会爆掉,所以,.0 或者 0.5 可能是分块读取的依据(当然你应该问一下数据在文本中是如何存储的
    magicyao
        70
    magicyao  
       303 天前
    很明显的桶排,然后取 1000 个,1000 是常数可以不计入复杂度中
    summerLast
        71
    summerLast  
       303 天前
    可以用桶 比如 200cm 对应第 4000 个桶 然后每个桶里这个身高对应的人数,找到满足条件的最大的几个桶的身高

    下一步就是如何用并发等提高入桶的统计速度,如先 xx 线程处理入桶,然后 xx 线程合并桶 几次迭代之后就有了上述的统计
    loryyang
        72
    loryyang  
       303 天前
    这种都老题了,其实没啥意思。知道解法会觉得很简单,不知道的,咋可能在面试的时候想出来。所以我面试从不出这种题目,不公平,没有筛选意义
    limitsy
        73
    limitsy  
       303 天前
    1 楼的意思应该也是哈希表吧?把身高上下限定为 0-3 米 转换为毫米 0-3000 ,然后可以建立一个长度为 3000 的整型数组(其实如果小数都是.0/.5 ,都不需要这么大的数组)。那么遍历身高,只需要把 arr[身高 * 10] ++ 。最后再从数组最大开始反向遍历取出前 1000 就可以了。
    picone
        74
    picone  
       303 天前
    @oamu 按照你这个说法,堆的大小只要是常数就不会影响时间复杂度?堆大小是 1000000 呢?
    leeraya
        75
    leeraya  
       303 天前
    典型的 topk 问题
    enson110
        76
    enson110  
       303 天前   ❤️ 1
    贴一个 GPT4 给的答案,是的真的强:

    ```
    如果你需要一个 O(n) 时间复杂度的解决方案,那么可以使用一个叫 "桶排序" 的技术。"桶排序" 是一种可以在线性时间内完成的排序算法,但是这需要对输入数据有一些特定的假设。

    根据你的问题描述,人的身高是以 0.5 的单位进行记录的。我们可以假设一个可能的范围,比如说从 0.0 到 300.0 。然后我们创建 600 个桶(一个桶代表 0.5 的身高),每个桶都对应了一个可能的身高。然后遍历所有的数据,根据身高将人放到对应的桶里。这一步的时间复杂度为 O(n)。

    接下来,我们可以从最高的桶开始,检查每个桶里有多少人。然后从这个桶开始向下找,直到找到 1000 个人。这一步的时间复杂度为 O(1),因为桶的数量是固定的。

    这样,整个算法的时间复杂度为 O(n)。需要注意的是,这种算法的效率取决于我们的假设是否准确,以及数据是否均匀分布。如果数据的分布很不均匀,桶排序的效率就会降低。

    这是一个基本的桶排序应用。如果需要处理更复杂的情况,比如说数据的范围不确定,或者桶的数量太多等,我们可能需要使用其他的技巧,比如说动态地创建桶等。但是基于你的问题描述,这个基本的方法应该就可以工作得很好。
    ```
    fdd92
        77
    fdd92  
       303 天前
    @picone 时间复杂度讨论的是总时间随项的增加而增加的情况,所以堆大小是常数就不影响时间复杂度。如果堆大小不是常数,那时间复杂度就是 O(n log m)。
    oamu
        78
    oamu  
       303 天前
    @picone #74 要比较前 1000 和前 1000000 , 实际上是把 1000 当作输入,那它也就不是常数了,用堆排序时间复杂度是最坏就是 O(n logk);但按照原题的条件和常识,可以知道可能的身高数量是有限的,且与数据规模(输入)无关,可以看成一个常数,每个身高最多插入堆 k 次,那么用堆排序最坏的时间复杂度应该是 O(n + k log k)。之前默认将 1000 看作常数是考虑不周。
    jameskongawork
        79
    jameskongawork  
       303 天前
    o(1) 人均 180
    buxudashi
        80
    buxudashi  
       303 天前
    这个,结果集其实是个链表。一个一个插入得了。

    [身高 2 米 4] =N 个人
    [身高 2 米 35] =M 个人
    wengyanbin
        81
    wengyanbin  
       303 天前
    人类的身高应该也是满足正态分布的,前 1000 占据 60 亿的比例,大体可以划出一个区间范围,作为过滤条件可以大幅度过滤掉不符合的
    jixiangqd
        82
    jixiangqd  
       303 天前
    这感觉像是脑筋急转弯。。。不过问题也许也是有些许应用价值的,可以作为种思路学习下
    iX8NEGGn
        83
    iX8NEGGn  
       303 天前 via iPhone
    类似词频统计,四层 trie 就能解决 ,第一层 0~3 (人的身高不会超过 3 米),第二层 0~9 ,第三层 0~9 ,第四层只有 0 和 5 ,每个 trie 节点有一个 count ,遍历一边 60 亿人的身高,每种身高有多少人就全得到了
    wangritian
        84
    wangritian  
       303 天前
    6L 并不是正解,8L 才是
    zengmingyang96
        85
    zengmingyang96  
       303 天前
    bitmap
    wwbfred
        86
    wwbfred  
       303 天前
    如果题目说身高都是整数,那么很容易就会想到统计每个身高对应的人数。出现半整数不改变题目本质,但具有迷惑性,让人更难想到最简单的方法。
    mrzhangrb
        87
    mrzhangrb  
       303 天前
    压根不用排序吧, 用哈希 key 为身高,val 为这个身高出现的次数, 遍历一遍, 从最高身高向下取 1000 个
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1211 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 23:14 · PVG 07:14 · LAX 16:14 · JFK 19:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.