scala 如何查找列表中的重复项?

vohkndzv  于 2023-08-05  发布在  Scala
关注(0)|答案(7)|浏览(210)

我有一个unsorted整数的列表,我想找到那些有重复项的元素。

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


有没有更简单的办法解决这个问题?

00jrzges

00jrzges1#

试试这个:

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 }


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

kiayqfof

kiayqfof2#

有点晚了,但这里有另一种方法:

dup.diff(dup.distinct).distinct

字符串
diff给出了参数(dup.distinct)中的所有额外项,这些项是重复项。

kmpatx3s

kmpatx3s3#

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

字符串

ktecyv1j

ktecyv1j4#

**总结:**我写了一个非常有效的函数,它返回List.distinctListList由每个出现一次以上的元素和元素重复出现的索引组成。
**详细信息:**如果您需要更多关于重复本身的信息,就像我一样,我已经编写了一个更通用的函数,它在List上迭代一次(因为顺序很重要),并返回一个Tuple2,其中包含删除的原始List(删除第一个之后的所有重复;即与调用distinct相同)和第二List,第二List示出了每个副本和它在原始List内出现的Int索引。

我已经基于general performance characteristics of the Scala collections实现了两次函数; 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)
}

字符串
下面是一个例子,可能会让它更直观一点。给定此String值列表:

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


如果你只想要副本,你只需要mapdupeAndIndexes调用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 s,考虑使用这个更高效的版本(它使用额外的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_._

34gzjxbg

34gzjxbg5#

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

字符串
我们首先将每个元素与false(Map阶段)相关联,一旦发现重复,我们就将其与true(缩减阶段)相关联。我们利用这样一个事实,即对于每个元素,只有当该元素是重复的时,才执行reduce阶段。然后,我们过滤,只保留与true相关联的元素(过滤阶段)。
这适用于trait Seq所有实现。
时间和空间复杂度均为O(n)

与其他答案比较:

1.@dhg answer不适用于所有类型的序列。例如,它适用于List,但会对Array产生不正确的结果(因为List模式匹配不会对Array起作用)。此外,尽管它具有相同的时间和空间复杂度,但它为每个元素创建了一个List,其中包含相应元素的所有副本,只是为了检查列表是否有多个元素。这意味着内存占用和运行时间会更高。
1.@Luigi Plinge的回答很好,很优雅。但是,它创建了一个类似于散列表的中间数据结构3次(diff为1次,distinct为2次),因此运行时间可能更高。

yhxst69z

yhxst69z6#

我要加入一个班轮派对。
不如这样:

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

字符串

bfhwhh0e

bfhwhh0e7#

我最喜欢的是

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

字符串

相关问题