首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
hua123s
V2EX  ›  问与答

提一个很弱智的问题

  •  
  •   hua123s · 212 天前 · 1365 次点击
    这是一个创建于 212 天前的主题,其中的信息可能已经有所发展或是发生改变。
    [1,2,3,4...1000000]
    [1,2,4,5...89234]
    

    两个数组元素都是 unique 的

    怎么比较高效地从一个数组去重另一个数组?

    15 条回复    2019-12-07 12:33:11 +08:00
    hua123s
        1
    hua123s   212 天前
    好像不应该叫去重,是从一个数组里面移除另一个数组
    Kilerd
        2
    Kilerd   212 天前   ❤️ 1
    第一个转 Set,然后遍历第二个,从第一个里面删掉。是 O(m n) ?
    emeab
        3
    emeab   212 天前   ❤️ 1
    array_diff()
    wish198
        4
    wish198   212 天前   ❤️ 1
    值做下标遍历两次?
    coderluan
        5
    coderluan   212 天前   ❤️ 1
    如果数字都是 int,就类似于 leetcode 第一题吧,顺便还能解决排序和去重问题,复杂度 O(m+n)。
    1.申请一个 bool 数组,长度是 1000000,用第一个数族初始化,有的话 1,没有的话 0。
    2.然后把第二个数组的数字当成下标去查这个 bool 数组,是 1 的话置 0。
    3.把最终的 bool 数组生成相应的 int 数组,也就是把步骤 1 反过来执行。
    littleylv
        6
    littleylv   212 天前   ❤️ 1
    是算法题还是实际情况?
    实际运用的话,一般语言都有内置的方法吧不用自己写,比如 PHP 的 https://www.php.net/manual/zh/function.array-diff.php
    LFUNWF
        7
    LFUNWF   212 天前   ❤️ 1
    numpy.setdiffld(x, y)
    LFUNWF
        8
    LFUNWF   212 天前   ❤️ 1
    @LFUNWF 上面打错了,是 numpy.setdiff1d(x, y)
    arvinsilm
        9
    arvinsilm   212 天前   ❤️ 1
    两个数组都是有序的? if(a[m] = b[n]) 移除,m++, n++; if(a[m] > b[n]) ,n++; if(a[m] < b[n]) m++。
    每个数组遍历一次,遍历过程中比较大小。
    hua123s
        10
    hua123s   212 天前
    @Kilerd O(mn)太惨了吧 。。
    hua123s
        11
    hua123s   212 天前
    @coderluan
    @arvinsilm
    其实想想好像挺简单的~~~2333
    across
        12
    across   212 天前 via iPhone   ❤️ 1
    你这个数组不仅是增序的,还是固定区间整数....
    逆向检索去重比计数法还快啊
    hua123s
        13
    hua123s   212 天前 via iPhone
    @across emmmm,可以伪代码?
    superrichman
        14
    superrichman   212 天前
    如果从开发效率上看我会选择 list(set(a) - set(b)) 就用 python 内置功能搞定, 实际开发过程如果不是关键的地方我会选择简单粗暴的方法. 手动狗头
    Kilerd
        15
    Kilerd   212 天前
    @hua123s #10 手机打字不知道怎么删多了,应该是 O(m+n)
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4353 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 07:37 · PVG 15:37 · LAX 00:37 · JFK 03:37
    ♥ Do have faith in what you're doing.