3

给定一个元素列表，其中一些元素重复多次，我需要生成一个带有元组的新列表，其中每个元组包含一个元素在一行中重复的次数和一个元素本身。

例如，给定

println(func(List()))              // should be empty list
println(func(List(1, 1)))          // (2,1) <- 1 is repeated 2 times
println(func(List(1, 1, 2, 1)))    // (2,1)(1,2)(1,1)

这是我目前最好的尝试。我觉得我缺少一些非常基本的东西，请帮助我理解什么

  def func[X](xs: List[X]): List[(Int, X)] = xs match {
    case Nil => Nil
    case y :: ys   => ys match {
      case Nil     => (1, y) :: Nil
      case z :: zs => if (y != z) (ys.prefixLength(_ == ys.head), y) :: func(ys) 
                      else func(ys)
    }
  }

在分析了问题所在之后，在我看来，当我递归调用时func(ys)，ys没有足够的信息来计算元素的数量。假设我们正在处理List(1,1,1,2). 好的，所以， y是1，z是1，(1::(2::Nil))是zs。按照我上面的逻辑，1 被看到 2 次的事实在下一次调用中丢失了。

问题可能是我没有以正确的方式思考这个问题。我想到的是“沿着列表走，直到你发现这个元素与以前的元素不同，此时，计算一个元素的出现次数并将其放入元组”）

我认识到在上述场景中（在我的代码中），问题是当数字实际上是相同的 (1,1) 时，我们已经看到一个数字的事实不会在任何地方反映出来。但是，鉴于我还没有准备好组成一个元组，请问在哪里可以做到这一点

在回答这个问题时，请坚持案例结构。我意识到可能还有其他更好、更清洁的方法来解决这个问题，我想更好地理解我在这里做错了什么

4

4 回答 4

8

你在正确的轨道上。问题是你不能在这里增量构建结果列表——你必须把头从递归调用中得到的列表中拉出来，并检查你是否需要添加一个新的对或增加最后一个的计数一：

def func[X](xs: List[X]): List[(Int, X)] = xs match {
  case Nil => Nil
  case y :: ys => func(ys) match {
    case (c, `y`) :: rest => (c + 1, y) :: rest
    case             rest => (    1, y) :: rest
  }
}

注意嵌套匹配模式中的反引号y——这对于避免只定义一个名为 的新变量是必要的y。

于 2013-01-27T20:07:09.850 回答
2

这是一个更简单的解决方案，使用span：

def runLength[T](xs: List[T]): List[(Int, T)] = xs match {
  case Nil => List()
  case x :: l => {
    val (front, back) = l.span(_ == x)
    (front.length + 1, x) :: runLength(back)
  }
}
于 2015-03-14T00:08:36.527 回答
1

它确实是游程编码。

这是一个简单但通用的尝试......

package rrs.scribble

object RLE {
  def rle[T](tSeq: List[T]): List[(Int, T)] = {
    def doRLE(seqT: List[T], rle: List[(Int, T)]): List[(Int, T)] =
      seqT match {
        case t :: moreT if t == rle.head._2 => doRLE(moreT, (rle.head._1 + 1, t) :: rle.tail)
        case t :: moreT => doRLE(moreT, (1, t) :: rle)
        case Nil => rle
      }

    if (tSeq.isEmpty)
      List.empty[(Int, T)]
    else
      doRLE(tSeq, List((0, tSeq.head))).reverse
  }
}

在 REPL 中：

scala> import rrs.scribble.RLE._
import rrs.scribble.RLE._

scala> rle(List(1, 1, 2, 1))
res0: List[(Int, Int)] = List((2,1), (1,2), (1,1))
于 2013-01-27T20:24:19.393 回答
-1

这称为游程编码。查看99 个 Scala 问题中的第 10 个问题（单击问题编号以获取解决方案）。

于 2013-01-27T19:33:00.063 回答