從一個列表中提取不在另一個列表中的元素

簡單地說，我有兩個列表，我需要提取添加到其中的新元素。我有以下從一個列表中提取不在另一個列表中的元素

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

從一個列表中提取不在另一個列表中的元素

回答

相關問題