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

Question

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

40

我有一个未排序的整数列表，我想找出其中拥有重复元素的元素。

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 } )

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

- Phil

7个回答

40

有点晚了，但这里提供另一种方法：

dup.diff(dup.distinct).distinct

diff会返回在参数dup.distinct之外的所有额外项，这些项都是重复的。

- Luigi Plinge

5

根据dup的类型，时间复杂度可能为O(N^2)。@dhg的答案是O(N)。 - pathikrit

2

@pathikrit 对于哪些类型的算法，时间复杂度会是O(N^2)？ - SlavaSt

1

就我个人而言，我不确定 groupBy 方法是 O(n) 还是 distinct 不是 O(n)。 - Luigi Plinge

4

另一种方法是使用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)

- Kigyo

3

摘要： 我编写了一个非常高效的函数，它返回List.distinct和一个由每个重复出现的元素及其重复出现的索引组成的List。

详细信息： 如果您需要更多关于重复项本身的信息，就像我一样，我编写了一个更通用的函数，该函数在一个List上进行迭代（因为排序很重要），仅执行一次，并返回一个Tuple2，其中包含原始List去重后的结果（所有第一次之后的重复项都被删除；即与调用distinct相同），以及第二个List，显示每个重复项及其在原始List中出现的Int索引。

我基于Scala集合的一般性能特征实现了两次函数; filterDupesL（其中L表示线性）和filterDupesEc（其中Ec表示有效常数）。

这是“线性”函数：

def filterDupesL[A](items: List[A]): (List[A], List[(A, Int)]) = {
  def recursive(
      remaining: List[A]
    , index: Int =
        0
    , accumulator: (List[A], List[(A, Int)]) =
        (Nil, Nil)): (List[A], List[(A, Int)]
  ) =
    if (remaining.isEmpty)
      accumulator
    else
      recursive(
          remaining.tail
        , index + 1
        , if (accumulator._1.contains(remaining.head)) //contains is linear
          (accumulator._1, (remaining.head, index) :: accumulator._2)
        else
          (remaining.head :: accumulator._1, accumulator._2)
      )
  val (distinct, dupes) = recursive(items)
  (distinct.reverse, dupes.reverse)
}

以下是一个例子，可能会让它更加直观。给定这个字符串值的列表：

val withDupes =
  List("a.b", "a.c", "b.a", "b.b", "a.c", "c.a", "a.c", "d.b", "a.b")

...然后执行以下操作：

val (deduped, dupeAndIndexs) =
  filterDupesL(withDupes)

...结果如下：

deduped: List[String] = List(a.b, a.c, b.a, b.b, c.a, d.b)
dupeAndIndexs: List[(String, Int)] = List((a.c,4), (a.c,6), (a.b,8))

如果你只想要重复的内容，你可以简单地在dupeAndIndexes上使用map并调用distinct：

val dupesOnly =
  dupeAndIndexs.map(_._1).distinct

...或者在单个调用中完成所有操作：

val dupesOnly =
  filterDupesL(withDupes)._2.map(_._1).distinct

如果更喜欢使用 Set，可以跳过 distinct 并调用 toSet 方法。

val dupesOnly2 =
  dupeAndIndexs.map(_._1).toSet

...或者在一个调用中完成所有操作：

val dupesOnly2 =
  filterDupesL(withDupes)._2.map(_._1).toSet

对于非常大的 List，考虑使用这个更高效的版本（它使用一个额外的 Set 在有效恒定时间内更改 contains 检查）：

这是“有效恒定”函数：

def filterDupesEc[A](items: List[A]): (List[A], List[(A, Int)]) = {
  def recursive(
      remaining: List[A]
    , index: Int =
        0
    , seenAs: Set[A] =
        Set()
    , accumulator: (List[A], List[(A, Int)]) =
        (Nil, Nil)): (List[A], List[(A, Int)]
  ) =
    if (remaining.isEmpty)
      accumulator
    else {
      val (isInSeenAs, seenAsNext) = {
        val isInSeenA =
          seenAs.contains(remaining.head) //contains is effectively constant
        (
            isInSeenA
          , if (!isInSeenA)
              seenAs + remaining.head
            else
              seenAs
        )
      }
      recursive(
          remaining.tail
        , index + 1
        , seenAsNext
        , if (isInSeenAs)
          (accumulator._1, (remaining.head, index) :: accumulator._2)
        else
          (remaining.head :: accumulator._1, accumulator._2)
      )
    }
  val (distinct, dupes) = recursive(items)
  (distinct.reverse, dupes.reverse)
}

上述两个函数都是我开源的Scala库ScalaOlio中filterDupes函数的改编版。它位于org.scalaolio.collection.immutable.List_._。

- chaotic3quilibrium

3

def findDuplicates[T](seq: Seq[T]): Seq[T] = {
  seq.groupMapReduce(identity)(_ => false)((_, _) => true).filter(_._2).keys.toSeq
}

我们首先将每个元素与false关联（映射阶段），一旦发现重复项，我们将其与true关联（减少阶段）。我们利用了这样一个事实：对于每个元素，只有在该元素是重复项时才进行减少阶段。然后我们过滤，只保留与true关联的元素（过滤阶段）。

这适用于Seq特质的所有实现。

时间和空间复杂度均为O(n)。

与其他答案比较：

@dhg的答案不适用于所有类型的序列。例如，它适用于List，但对于Array会产生错误的结果（因为List模式匹配无法在Array上运行）。虽然它具有相同的时间和空间复杂度，但它为每个包含相应元素的所有重复项的元素创建一个List，仅检查该列表是否具有多个元素。这意味着内存占用和运行时间将更高。
@Luigi Plinge的答案很好而且优雅。但是，它会3次创建中间类似哈希表的数据结构（1次用于diff，2次用于distinct），因此运行时间可能会更长。

- SlavaSt

这是我个人认为最清晰和高效的解决方案，我的问题是为什么不直接检查组的长度，像这样： seq.groupBy(identity).filter(_._2.length > 1).keys.toSeq？ - David Perlman

1

@DavidPerlman你可以这样做，但效率较低。这可能是一个考虑因素，具体取决于你的使用情况。 seq.groupBy(identity)会为每个值创建一个包含所有重复项的Seq。我们不使用该序列，只需检查其长度。相反，groupMapReduce不会创建这样的序列。 - SlavaSt

1

我将参加一行代码派对。

这样行吗:

这个怎么样:

(myDupList zip myDupList.tail).filter((m,n) => (m==n)).map((m,n) => m)

- sudheer sid

0

我的最爱是

def hasDuplicates(in: List[Int]): Boolean = {
  val sorted = in.sortWith((i, j) => i < j)
  val zipped = sorted.tail.zip(sorted)
  zipped.exists(p => p._1 == p._2)
}

- user8221989

4

欢迎来到SO！我们通常建议在您的代码中添加解释，以便提问者更好地理解您的答案。尽可能避免只有代码而缺少解释的回答。 - JNYRanger

3

这并不能达到提问者的要求，他想要找到重复项，而不仅仅是检测是否存在一些重复项。 - The Archetypal Paul

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dhg · Accepted Answer

试试这个：

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 后面的匹配模式将匹配与符合 List(_,_,_*) 模式的列表相关联的整数 x，即至少有两个元素的列表，每个元素由下划线表示，因为我们实际上不需要存储这些值（这两个元素后面可以跟随零个或多个元素：_*）。

你还可以这样做：

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

它比你提供的方法要快得多，因为它不必反复传递数据。