Scala – 将两个序列组合成连续增加的三元组

发布时间：2020-12-16 08:44:35 所属栏目：安全来源：网络整理

导读：解决以下问题的有效方法是什么？在命令式的风格中,这可以在线性时间内完成. 给定两个排序的序列p和q,f返回三元组的序列r(或任何集合),其中对于r中的每个三元组(a,b,c),以下保持： (a b c) 以下两个中的一个： a,c是两个连续的元素p,b是q a,c是两个连续的元素

解决以下问题的有效方法是什么？在命令式的风格中,这可以在线性时间内完成.

给定两个排序的序列p和q,f返回三元组的序列r(或任何集合),其中对于r中的每个三元组(a,b,c),以下保持：

>(a< b< c)
>以下两个中的一个：

> a,c是两个连续的元素p,b是q
> a,c是两个连续的元素q,b是p

示例：考虑以下两个序列.

val p = Seq(1,4,5,7,8,9)
val q = Seq(2,3,6,10)

然后f(p,s)计算以下序列：

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

目前的解决方案：我觉得这个非常优雅.我正在寻找一个更好的.

def consecutiveTriplesOneWay(s1: Seq[Int],s2:Seq[Int]) = {
        for {
            i <- 0 until s1.size - 1 if s1(i) < s1(i+1)
            j <- 0 until s2.size if s1(i) < s2(j) &&  s2(j) < s1(i+1)
        } yield (s1(i),s2(j),s1(i+1))
    }

    def consecutiveTriples(s1: Seq[Int],s2:Seq[Int]) =
        consecutiveTriplesOneWay(s1,s2) ++ consecutiveTriplesOneWay(s2,s1)

    def main(args: Array[String]) {
        val p = Seq(1,9)
        val q = Seq(2,10)

        consecutiveTriples(p,q).foreach(println(_))
    }

编辑：我的必要解决方案

def consecutiveTriplesOneWayImperative(s1: Seq[Int],s2:Seq[Int]) = {
    var i = 0
    var j = 0
    val triples = mutable.MutableList.empty[(Int,Int,Int)]
    while (i < s1.size - 1 && j < s2.size) {
        if (s1(i) < s2(j) && s2(j) < s1(i + 1)) {
            triples += ((s1(i),s1(i + 1)))
            j += 1
        } else if (s1(i) >= s2(j))
            j += 1
        else
            i += 1
    }
    triples.toSeq
}

def consecutiveTriples(s1: Seq[Int],s2:Seq[Int]) = 
    consecutiveTriplesOneWayImperative(s1,s2) ++ 
            consecutiveTriplesOneWayImperative(s2,s1)

解决方法

势在必行的解决方案转化为tailrec.比特冗长但有效

def consecutiveTriplesRec(s1: Seq[Int],s2: Seq[Int]) = {
  @tailrec
  def consTriplesOneWay(left: Seq[Int],right: Seq[Int],triples: Seq[(Int,Int)]): Seq[(Int,Int)] = {
    (left,right) match {
      case (l1 :: l2 :: ls,r :: rs) =>
        if (l1 < r && r < l2) consTriplesOneWay(left,rs,(l1,r,l2) +: triples)
        else if (l1 >= r) consTriplesOneWay(left,triples)
        else consTriplesOneWay(l2 :: ls,right,triples)
      case _ => triples
    }
  }
  consTriplesOneWay(s1,s2,Nil) ++ consTriplesOneWay(s2,s1,Nil)
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!