Wie können Sie 2 oder mehr Duplikate aus der Liste entfernen und ihre ursprüngliche Reihenfolge beibehalten?

Question

Hier können wir eine Scala Liste übernehmen haben:

val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 

Wir Duplikate leicht entfernen können mit dem folgenden Code:

l1.distinct 

oder

l1.toSet.toList 

Aber was, wenn wir Duplikate entfernen möchten nur wenn es mehr als 2 von ihnen gibt? Wenn also mehr als 2 Elemente mit demselben Wert vorhanden sind, bleiben wir nur zwei und entfernen den Rest von ihnen.

Ich konnte es mit folgenden Code erreichen:

l1.groupBy(identity).mapValues(_.take(2)).values.toList.flatten 

, die mir das Ergebnis gab:

List(2, 2, 5, 1, 1, 3, 3) 

Elemente entfernt werden, aber die Reihenfolge der übrigen Elemente unterscheidet sich von, wie diese Elemente erschienen in der erste Liste. Wie man diese Operation durchführt und die Reihenfolge von der ursprünglichen Liste bleibt?

So sollte das Ergebnis für l1 sein:

List(1, 2, 3, 1, 3, 2, 5) 

Answer 1

nicht die effizienteste.

scala> val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 
l1: List[Int] = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 

scala> l1.zipWithIndex.groupBy(_._1).map(_._2.take(2)).flatten.toList.sortBy(_._2).unzip._1 
res10: List[Int] = List(1, 2, 3, 1, 3, 2, 5) 

Answer 2

nicht die schönste. Ich freue mich auf die anderen Lösungen.

def noMoreThan(xs: List[Int], max: Int) = 
{ 
    def op(m: Map[Int, Int], a: Int) = { 
    m updated (a, m(a) + 1) 
    } 
    xs.scanLeft(Map[Int,Int]().withDefaultValue(0)) (op).tail 
    .zip(xs) 
    .filter{ case (m, a) => m(a) <= max } 
    .map(_._2) 
} 

scala> noMoreThan(l1, 2) 
res0: List[Int] = List(1, 2, 3, 1, 3, 2, 5) 

Answer 3

Hier ist eine rekursive Lösung (es wird Überlauf für große Listen Stack):

def filterAfter[T](l: List[T], max: Int): List[T] = { 
    require(max > 1) 
    //keep the state of seen values 
    val seen = Map[T, Int]().withDefaultValue(0)//init to 0 
    def filterAfter(l: List[T], seen: Map[T, Int]): (List[T], Map[T, Int]) = { 
     l match { 
     case x :: xs => 
      if (seen(x) < max) { 
      //Update the state and pass to next 
      val pair = filterAfter(xs, seen updated (x, seen(x) + 1)) 
      (x::pair._1, pair._2) 
      } else { 
      //already seen more than max 
      filterAfter(xs, seen) 
      } 
     case _ => (l, seen)//empty, terminate recursion 
     } 
    } 
    //call inner recursive function 
    filterAfter(l, seen, 2)._1 
    } 

Answer 4

auf experquisite Antwort basiert, aber mit foldLeft:

def noMoreThanBis(xs: List[Int], max: Int) = { 
    val initialState: (Map[Int, Int], List[Int]) = (Map().withDefaultValue(0), Nil) 
    val (_, result) = xs.foldLeft(initialState) { case ((count, res), x) => 
    if (count(x) >= max) 
     (count, res) 
    else 
     (count.updated(x, count(x) + 1), x :: res) 
    } 
    result.reverse 
} 

Answer 5

Meine bescheidene Antwort:

def distinctOrder[A](x:List[A]):List[A] = { 
    @scala.annotation.tailrec 
    def distinctOrderRec(list: List[A], covered: List[A]): List[A] = { 
     (list, covered) match { 
     case (Nil, _) => covered.reverse 
     case (lst, c) if c.count(_ == lst.head) >= 2 => distinctOrderRec(list.tail, covered) 
     case _ => distinctOrderRec(list.tail, list.head :: covered) 
     } 
    } 
    distinctOrderRec(x, Nil) 
} 

Mit den Ergebnissen:

scala> val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 
l1: List[Int] = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 

scala> distinctOrder(l1) 
res1: List[Int] = List(1, 2, 3, 1, 3, 2, 5) 

On Edit: Kurz bevor ich zu Bett ging, kam ich auf diese Idee!

l1.foldLeft(List[Int]())((total, next) => if (total.count(_ == next) >= 2) total else total :+ next) 

mit einer Antwort von:

res9: List[Int] = List(1, 2, 3, 1, 3, 2, 5) 

Answer 6

einfachere Version mit foldLeft:

l1.foldLeft(List[Int]()){(acc, el) => 
    if (acc.count(_ == el) >= 2) acc else el::acc}.reverse 

Answer 7

Ähnlich wie verschiedene implemeted ist, mit einem multiset anstelle eines Satzes:

def noMoreThan[T](list : List[T], max : Int) = { 
    val b = List.newBuilder[T] 
    val seen = collection.mutable.Map[T,Int]().withDefaultValue(0) 
    for (x <- list) { 
     if (seen(x) < max) { 
     b += x 
     seen(x) += 1 
     } 
    } 
    b.result() 
    } 

Answer 8

Wie wäre es damit:

list 
.zipWithIndex 
.groupBy(_._1) 
.toSeq 
.flatMap { _._2.take(2) }  
.sortBy(_._2) 
.map(_._1) 

Answer 9

Es ist ein bisschen hässlich, aber es ist relativ schneller

val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1) 
l1.foldLeft((Map[Int, Int](), List[Int]())) { case ((m, ls), x) => { 
    val z = m + ((x, m.getOrElse(x, 0) + 1)) 
    (z, if (z(x) <= 2) x :: ls else ls) 
}}._2.reverse 

Gibt: List(1, 2, 3, 1, 3, 2, 5)

Answer 10

Hier kanonische Scala-Code ist eine Reihe zu mindern drei oder mehr um zwei in einer Reihe:

def checkForTwo(candidate: List[Int]): List[Int] = { 
    candidate match { 
     case x :: y :: z :: tail if x == y && y == z => 
     checkForTwo(y :: z :: tail) 
     case x :: tail => 
     x :: checkForTwo(tail) 
     case Nil => 
     Nil 
    } 
    } 

Es sieht die ersten drei ele Wenn sie identisch sind, wird die erste gelöscht und der Vorgang wiederholt. Andernfalls gibt es Elemente weiter.

Answer 11

distinct definiert für SeqLike als

/** Builds a new $coll from this $coll without any duplicate elements. 
* $willNotTerminateInf 
* 
* @return A new $coll which contains the first occurrence of every element of this $coll. 
*/ 
def distinct: Repr = { 
    val b = newBuilder 
    val seen = mutable.HashSet[A]() 
    for (x <- this) { 
    if (!seen(x)) { 
     b += x 
     seen += x 
    } 
    } 
    b.result() 
} 

Wir haben unsere Funktion in sehr ähnlicher Weise definieren:

def distinct2[A](ls: List[A]): List[A] = { 
    val b = List.newBuilder[A] 
    val seen1 = mutable.HashSet[A]() 
    val seen2 = mutable.HashSet[A]() 
    for (x <- ls) { 
    if (!seen2(x)) { 
     b += x 
     if (!seen1(x)) { 
     seen1 += x 
     } else { 
     seen2 += x 
     } 
    } 
    } 
    b.result() 
} 

scala> distinct2(l1) 
res4: List[Int] = List(1, 2, 3, 1, 3, 2, 5) 

Diese Version internen Zustand verwendet, ist aber noch rein. Es ist auch ziemlich einfach, für beliebige n (derzeit 2) zu verallgemeinern, aber spezifische Version ist leistungsfähiger.

Sie können dieselbe Funktion mit Falzen implementieren, die den Status "Was ist einmal und zweimal zu sehen" mitnehmen. Doch der for-Schleife und veränderbare Zustand macht den gleichen Job.

Answer 12

Lösung mit groupBy und Filter, ohne Sortierung (es ist also O (N), Sortieren Sie die O (Nlog (N)) im typischen Fall geben):

val li = l1.zipWithIndex 
val pred = li.groupBy(_._1).flatMap(_._2.lift(1)) //1 is your "2", but - 1 
for ((x, i) <- li if !pred.get(x).exists(_ < i)) yield x 

Answer 13

ich mit unveränderlichen Ansatz bevorzugen Map:

def noMoreThan[T](list: List[T], max: Int): List[T] = { 
    def go(tail: List[T], freq: Map[T, Int]): List[T] = { 
     tail match { 
     case h :: t => 
      if (freq(h) < max) 
      h :: go(t, freq + (h -> (freq(h) + 1))) 
      else go(t, freq) 
     case _ => Nil 
     } 
    } 
    go(list, Map[T, Int]().withDefaultValue(0)) 
    }