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

提一个很弱智的问题

  •  
  •   hua123s · 2019-12-06 16:48:13 +08:00 · 2084 次点击
    这是一个创建于 1575 天前的主题,其中的信息可能已经有所发展或是发生改变。
    [1,2,3,4...1000000]
    [1,2,4,5...89234]
    

    两个数组元素都是 unique 的

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

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