这是一个创建于 1810 天前的主题，其中的信息可能已经有所发展或是发生改变。
[1,2,3,4...1000000]
[1,2,4,5...89234]
两个数组元素都是 unique 的
怎么比较高效地从一个数组去重另一个数组？
 |
1
hua123s OP 好像不应该叫去重，是从一个数组里面移除另一个数组
|
 |
2
Kilerd 2019-12-06 17:21:38 +08:00  1
第一个转 Set，然后遍历第二个，从第一个里面删掉。是 O(m n) ？
|
 |
3
2kCS5c0b0ITXE5k2 2019-12-06 17:22:25 +08:00 1
array_diff()
|
 |
4
wish198 2019-12-06 17:24:32 +08:00 1
值做下标遍历两次?
|
 |
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 反过来执行。 |
 |
6
littleylv 2019-12-06 17:32:08 +08:00 1
是算法题还是实际情况？
实际运用的话，一般语言都有内置的方法吧不用自己写，比如 PHP 的 https://www.php.net/manual/zh/function.array-diff.php |
 |
7
LFUNWF 2019-12-06 18:53:26 +08:00 1
numpy.setdiffld(x, y)
|
 |
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++。
每个数组遍历一次，遍历过程中比较大小。 |
 |
12
across 2019-12-06 19:16:07 +08:00 via iPhone 1
你这个数组不仅是增序的，还是固定区间整数....
逆向检索去重比计数法还快啊 |
 |
14
superrichman 2019-12-06 19:55:09 +08:00
如果从开发效率上看我会选择 list(set(a) - set(b)) 就用 python 内置功能搞定, 实际开发过程如果不是关键的地方我会选择简单粗暴的方法. 手动狗头
|
Select Language