提一个很弱智的问题

[hua123s]

[1,2,3,4...1000000]
[1,2,4,5...89234]

两个数组元素都是 unique 的

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

[hua123s]

好像不应该叫去重，是从一个数组里面移除另一个数组

[Kilerd]

第一个转 Set，然后遍历第二个，从第一个里面删掉。是 O(m n) ？

[2kCS5c0b0ITXE5k2]

array_diff()

[wish198]

值做下标遍历两次?

[coderluan]

如果数字都是 int，就类似于 leetcode 第一题吧，顺便还能解决排序和去重问题，复杂度 O(m+n)。
1.申请一个 bool 数组，长度是 1000000，用第一个数族初始化，有的话 1，没有的话 0。
2.然后把第二个数组的数字当成下标去查这个 bool 数组，是 1 的话置 0。
3.把最终的 bool 数组生成相应的 int 数组，也就是把步骤 1 反过来执行。

[U7Q5tLAex2FI0o0g]

是算法题还是实际情况？
实际运用的话，一般语言都有内置的方法吧不用自己写，比如 PHP 的 https://www.php.net/manual/zh/function.array-diff.php

[LFUNWF]

numpy.setdiffld(x, y)

[LFUNWF]

@LFUNWF 上面打错了，是 numpy.setdiff1d(x, y)

[arvinsilm]

两个数组都是有序的？ if(a[m] = b[n]) 移除，m++, n++； if(a[m] > b[n]) ，n++； if(a[m] < b[n]) m++。
每个数组遍历一次，遍历过程中比较大小。

[hua123s]

@Kilerd O(mn)太惨了吧 。。

[hua123s]

@coderluan
@arvinsilm
其实想想好像挺简单的~~~2333

[across]

你这个数组不仅是增序的，还是固定区间整数....
逆向检索去重比计数法还快啊

[hua123s]

@across emmmm，可以伪代码？

[superrichman]

如果从开发效率上看我会选择 list(set(a) - set(b)) 就用 python 内置功能搞定, 实际开发过程如果不是关键的地方我会选择简单粗暴的方法. 手动狗头

[Kilerd]

@hua123s #10 手机打字不知道怎么删多了，应该是 O(m+n)