如何在列表中查找重复项？

Question

我有一个未排序的整数列表,我想找到那些有重复的元素.

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)

我可以使用dup.distinct找到集合的不同元素,所以我写了如下答案.

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
val distinct = dup.distinct
val elementsWithCounts = distinct.map( (a:Int) => (a, dup.count( (b:Int) => a == b )) )
val duplicatesRemoved = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 <= 1 } )
val withDuplicates = elementsWithCounts.filter( (pair: Pair[Int,Int]) => { pair._2 > 1 } )

有没有更简单的方法来解决这个问题？

Answer 1

试试这个:

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)
dup.groupBy(identity).collect { case (x, List(_,_,_*)) => x }

该groupBy联营公司与它出现的列表中的每个不同的整数.的collect基本上是map其中非匹配元素被忽略.下面的匹配模式case将匹配x与适合模式List(_,_,_*)的列表相关联的整数,一个包含至少两个元素的列表,每个元素由下划线表示,因为我们实际上不需要存储这些值(并且可以遵循这两个元素由零个或多个元素组成:) _*.

你也可以这样做:

dup.groupBy(identity).collect { case (x,ys) if ys.lengthCompare(1) > 0 => x }

它比您提供的方法快得多,因为它不必重复传递数据.

Answer 2

派对有点晚了,但这是另一种方法:

dup.diff(dup.distinct).distinct

diff为你提供了参数(dup.distinct)中所有额外的项目,它们是重复项.

Answer 3

另一种方法是使用foldLeft困难的方法。

我们从两个空集开始。一种是我们至少见过一次的元素。另一个用于我们至少见过两次的元素（也称为重复项）。

我们遍历列表。当当前元素已被看到 ( seen(cur)) 时，它是重复的，因此被添加到duplicates。否则我们将其添加到seen. 现在的结果是包含重复项的第二组。

我们也可以将其写为通用方法。

def dups[T](list: List[T]) = list.foldLeft((Set.empty[T], Set.empty[T])){ case ((seen, duplicates), cur) => 
  if(seen(cur)) (seen, duplicates + cur) else (seen + cur, duplicates)      
}._2

val dup = List(1,1,1,2,3,4,5,5,6,100,101,101,102)

dups(dup) //Set(1,5,101)