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

一道求中位数的面试题

  •  
  •   yujianwjj · 2020-03-12 19:18:21 +08:00 · 3040 次点击
    这是一个创建于 1476 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个数组,不停的往里面添加数字,要求 O(1) 复杂度求数组中位数。

    13 条回复    2020-03-12 21:55:28 +08:00
    hcocoa
        1
    hcocoa  
       2020-03-12 19:40:13 +08:00
    空间换时间
    imn1
        2
    imn1  
       2020-03-12 20:11:43 +08:00
    你这“中位数”是数学的中位数定义么——(最大值+最小值)/2 ?
    如果是的话,只需要比较初始最大最小值和添加值而已啊
    chibupang
        3
    chibupang  
       2020-03-12 20:15:00 +08:00 via iPhone
    用最大堆最小堆分别存一半的数据,再往后,答案就很明显了。
    liyunlong41
        4
    liyunlong41  
       2020-03-12 20:28:45 +08:00 via iPhone   ❤️ 1
    添加的时候实时计算中位数即可,比如一开始有一个数,中位数就是这个数下标,然后根据中位数和添加的数的大小比较,确定中位数应该往左移还是右移,实时维护中位数位置。
    yujianwjj
        5
    yujianwjj  
    OP
       2020-03-12 20:35:13 +08:00
    @chibupang 懂了
    noqwerty
        6
    noqwerty  
       2020-03-12 20:43:34 +08:00 via Android
    @imn1 中位数不是这么定义的啊大兄弟
    fishCatcher
        7
    fishCatcher  
       2020-03-12 20:52:27 +08:00 via iPhone
    @chibupang 可是每次插入新数时,调整要 O(logn)啊?
    imn1
        8
    imn1  
       2020-03-12 21:22:49 +08:00
    @noqwerty #6
    那就是统计学的中位数了
    不过也是,面试题也不会这么简单~
    inhzus
        10
    inhzus  
       2020-03-12 21:43:56 +08:00
    @fishCatcher #7 两个函数,插入 O(logn),计算中位数 O(1)。楼主说的 O(1) 应该指的是后者的时间复杂度
    pipapa
        11
    pipapa  
       2020-03-12 21:44:07 +08:00
    @imn1 统计学也不是这样定义的吧
    yclissetj
        12
    yclissetj  
       2020-03-12 21:54:52 +08:00 via iPad
    原题没给出时间复杂度的要求,题解里最好也是 O(nlogn) 呀 。。
    https://leetcode.com/problems/find-median-from-data-stream/
    yclissetj
        13
    yclissetj  
       2020-03-12 21:55:28 +08:00 via iPad
    @yclissetj sorry,O(logn) ...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3512 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:48 · PVG 18:48 · LAX 03:48 · JFK 06:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.