Предположим, что у нас есть список Scala:
val l1 = List(1, 2, 3, 1, 1, 3, 2, 5, 1)
Мы можем легко удалить дубликаты, используя следующий код:
l1.distinct
или
l1.toSet.toList
Но что, если мы хотим удалить дубликаты, только если их более двух? Поэтому, если имеется более двух элементов с одинаковым значением, мы остаемся только двумя и удаляем остальные из них.
Я мог бы добиться этого с помощью следующего кода:
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)
Не самый эффективный.
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)
Мой скромный ответ:
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)
Не самый красивый. Я с нетерпением жду других решений.
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)
Более простая версия с использованием foldLeft:
l1.foldLeft(List[Int]()){(acc, el) =>
if (acc.count(_ == el) >= 2) acc else el::acc}.reverse
Аналогично тому, как различен реализованный, с мультимножеством вместо набора:
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()
}
На основе экспериментального ответа, но используя 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
}
Как насчет этого:
list
.zipWithIndex
.groupBy(_._1)
.toSeq
.flatMap { _._2.take(2) }
.sortBy(_._2)
.map(_._1)
distinct определяется для SeqLike как
/** 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()
}
Мы можем точно определить нашу функцию:
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)
Эта версия использует внутреннее состояние, но по-прежнему чиста. Также довольно легко обобщить для произвольного n (в настоящее время 2), но конкретная версия более эффективна.
Вы можете реализовать ту же функцию, что и складки, несущие с собой "то, что видно один раз и два". Тем не менее, цикл for и изменяемое состояние выполняют ту же работу.
Его немного уродливый, но его относительно быстрый
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
Дает: List(1, 2, 3, 1, 3, 2, 5)
Вот рекурсивное решение (оно будет стекать переполнение для больших списков):
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
}
Вот канонический Scala код, чтобы уменьшить три или более строки в две строки:
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
}
}
Он смотрит на первые три элемента списка, и если они одинаковые, то выпадает первый и повторяется процесс. В противном случае он передает элементы через.
Решение с groupBy и фильтром без сортировки (так что O (N), сортировка даст вам дополнительный O (Nlog (N)) в типичном случае):
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
Я предпочитаю подход с неизменяемым 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))
}