Как найти дубликаты в списке?

Ответ 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 }

Это намного быстрее, чем предлагаемый вами подход, поскольку ему не нужно многократно передавать данные.

Ответ 2

Немного поздно для вечеринки, но здесь другой подход:

dup.diff(dup.distinct).distinct

diff дает вам все дополнительные элементы выше тех, что указаны в аргументе (dup.distinct), которые являются дубликатами.

Ответ 3

Резюме: Я написал очень эффективную функцию, которая возвращает как List.distinct, так и List, состоящую из каждого элемента, который появился более одного раза, и индекс, в котором появился дубликат элемента.

Детали: Если вам нужно немного больше информации о самих дубликатах, как и я, я написал более общую функцию, которая повторяется через List (как упорядочение была значительна) ровно один раз и возвращает Tuple2, состоящую из оригинала List debuped (все дубликаты после первого удаляются, то есть то же самое, что и вызов distinct), и второй List, показывающий каждый дубликат и индекс Int, в котором он произошел в исходном List.

Я реализовал эту функцию дважды на основе общих характеристик производительности 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)
}

Ниже приведен пример, который может сделать его более интуитивным. Учитывая этот список значений 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))

И если вам просто нужны дубликаты, вы просто map через dupeAndIndexes и вызываете distinct:

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

... или все за один вызов:

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

... или если a 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)
}

Обе эти функции являются адаптацией функции filterDupes в моей открытой библиотеке Scala, ScalaOlio. Он расположен в org.scalaolio.collection.immutable.List_._.

Ответ 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)

Ответ 5

Мой любимый

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