从一个列表中提取不在另一个列表中的元素

简单地说，我有两个列表，我需要提取添加到其中的新元素。我有以下从一个列表中提取不在另一个列表中的元素

val x = List(1,2,3) 
val y = List(1,2,4) 

val existing :List[Int]= x.map(xInstance => { 
     if (!y.exists(yInstance => 
     yInstance == xInstance)) 
     xInstance 
    }) 

Result :existing: List[AnyVal] = List((),(), 3)

我需要删除除了以最小的成本数字的所有其他元素。

来源

2012-03-04 Echo

最简单的方法是使用filter代替没有什么捞出;

val existing :List[Int] = 
    x.filter(xInstance => !y.exists(yInstance => yInstance == xInstance))

来源

2012-03-04 22:39:33

注意：'exists'和'filter'是'O（N）'，所以这个combi这里的国家是'O（N^2）' – retronym 2012-03-04 22:41:37

@retronym好的一点是，设置的解决方案肯定是更有效的解决方案，我只是尽可能地与原始代码相提并论。 – 2012-03-04 22:44:14

同样的事情，但更漂亮：'x.filterNot（y.contains）' – elbowich 2012-03-05 05:41:08

val existing = x.filter(d => !y.exists(_ == d))

existing: List[Int] = List(3)

来源

2012-03-04 22:39:11 dotoree

选择一个合适的数据结构，生活变得更容易。

scala> x.toSet -- y 
res1: scala.collection.immutable.Set[Int] = Set(3)

另外注意的是：

if (condition) expr1

简写为：

if (condition) expr1 else()

使用这样的结果，通常都会有静态类型Any或AnyVal几乎总是错误。它只适用于副作用：

if (condition) buffer += 1 
if (condition) sys.error("boom!")

来源

2012-03-04 22:39:58 retronym

太棒了!!!!! – dotoree 2012-03-04 22:45:54

retronym的解决方案是好的如果你没有重复的元素，你不关心的顺序。但是，你并不是说这是事实。

因此，将y转换为集合（而不是x）可能是最有效的。我们只需要遍历该列表一次，并且对该集合具有快速的O（log（n））访问权限。

所有你需要的是

x filterNot y.toSet 
// res1: List[Int] = List(3)

编辑：

此外，还有一个内置的方法就更简单了：

x diff y

（我有一个看的执行情况;它看起来非常高效，使用HashMap来计算出现次数。）

来源

2012-03-04 23:40:58

不错。读者不应该说'Set [T]'实现'T => Boolean'。 – retronym 2012-03-05 08:20:38

从一个列表中提取不在另一个列表中的元素

回答

相关问题