如何从列表中删除2个或更多重复项并保持其初始订单？

Question

让我们假设我们有一个Scala列表:

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

我们可以使用以下代码轻松删除重复项:

l1.distinct

要么

l1.toSet.toList

但是,如果我们想要删除重复项,只有当它们超过2个时呢？因此,如果有两个以上具有相同值的元素,我们只保留两个并删除其余元素.

我可以使用以下代码实现它:

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

这给了我结果:

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

元素被删除但剩余元素的顺序与这些元素在初始列表中的显示方式不同.如何执行此操作并保留原始列表中的顺序？

所以l1的结果应该是:

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

Answer 1

不是最有效的.

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

我的谦虚回答:

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

结果如下:

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)

编辑:就在我上床睡觉之前,我想出了这个!

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

答案是:

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

Answer 3

不是最漂亮的.我期待看到其他解决方案.

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 4

使用foldLeft更直接的版本:

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

Answer 5

类似于如何实现distinct,使用multiset而不是set:

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