12

我正在尝试合并两个序列，以使它们保持排序。以下是我编写的代码：

  val seq1 = Seq(1,3,5,7,9)
  val seq2 = Seq(2,4,6,8)
  var arr = Seq[Int]()
  for(b <- seq2)
  {
    for(a <- seq1)
    {
      if(a < b)
        arr = arr :+ a
      else
      {
        arr = arr :+ b;break; 
      }
    }
  }
  println(arr)

我需要的输出需要是：

Seq(1,2,3,4,5,6,7,8,9)

但似乎 break 在 Scala 中不起作用。我对这门语言比较陌生。执行此操作的最佳方法是什么？

4

5 回答 5

25

最简单的方法可能是这样的：

(seq1 ++ seq2).sorted

如果seq1并且seq2包含其他类型，则必须Ordering为该类型提供一个；或者，或者，使用该sortBy方法，将每个元素映射到Ordering可以隐式找到的另一种类型的元素：

(seq1 ++ seq2).sortBy(_.toDate)
于 2013-10-18T07:41:29.123 回答
8

以下也适用于非交错序列：

def mergeSorted[E: Ordering](x: Seq[E], y: Seq[E]): Seq[E] = {
  val ordering = implicitly[Ordering[E]]
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Seq[E]): Seq[E] = {
    (x, y) match {
      case (Nil, Nil) => acc
      case (_, Nil)   => acc ++ x
      case (Nil, _)   => acc ++ y
      case (xh :: xt, yh :: yt) =>
        if (ordering.lteq(xh, yh))
          rec(xt, y, acc :+ xh)
        else
          rec(x, yt, acc :+ yh)
    }
  }
  rec(x, y, Seq())
}

请注意，出于性能原因，您可能会使用构建器（与 :+、+:、反向）。

于 2013-10-18T14:34:50.137 回答
6

我很高兴找到@CaringDev 的解决方案并将其调整为使用Builder：

def mergeSortedBuilder[E: Ordering](x: Seq[E], y: Seq[E])(implicit ordering: Ordering[E]): Seq[E] = {
  @tailrec
  def rec(x: Seq[E], y: Seq[E], acc: Builder[E, Seq[E]]): Builder[E, Seq[E]] = {
  (x, y) match {
    case (Nil, Nil) => acc
    case (_, Nil)   => acc ++= x
    case (Nil, _)   => acc ++= y
    case (xh :: xt, yh :: yt) =>
      if (ordering.lteq(xh, yh))
        rec(xt, y, acc += xh)
      else
        rec(x, yt, acc += yh)
  }
}
rec(x, y, Seq.newBuilder).result
}
于 2016-11-13T15:46:58.843 回答
1

要交错两个序列，同时保持它们各自的顺序，您可以使用：

scala> seq1.zip(seq2).flatMap(pair => Seq(pair._1,pair._2))
res1: Seq[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

但是请注意，对于长度不等的序列，这会丢失较长序列的额外元素。这可以通过更多的努力来解决（找到两个列表中较长的一个，然后添加longer.drop(shorter.length)）。

于 2013-10-18T07:43:59.437 回答
0

如果你想按顺序交错任意数量的序列，你可以使用类似的东西

implicit class Interleave[T](input: Seq[Seq[T]]) {
  def interleave: Seq[T] = {
    input.foldLeft(Seq[Seq[T]]()) { (acc, cur) =>
      if (acc.isEmpty) cur.map { m => Seq(m) }
      else (acc zip cur).map { case (sequence, m) =>
        sequence :+ m
      }
    }.flatten.toVector
  }
}

有可能提高这方面的性能，特别是因为toVector它主要是为了将流转换为渴望的东西。

用法看起来像

Seq(Seq(1,2), Seq(2,3), Seq(3,4)).interleave should be(Seq(1,2,3,2,3,4))
于 2019-01-11T01:51:15.947 回答