0

我正在尝试使用合并排序在 Scala 中进行倒数计数并且无法取得进展，因为其中一种方法是抛出 IndexOutOfBoundsException 以将空列表作为参数传递。

def sortAndCountInv(il: List[Int]): Int = {

def mergeAndCountInv(ll: List[Int], rl: List[Int]): (List[Int], Int) = {
  println("mergeAndCountInv : ")
  if (ll.isEmpty && !rl.isEmpty) (rl, 0)
  if (rl.isEmpty && !ll.isEmpty) (ll, 0)
  if (ll.isEmpty && rl.isEmpty) (List(), 0)
  if (ll(0) <= rl(0)) {

    val x = mergeAndCountInv(ll.tail, rl)//*passing empty list, ll.tail invoking IndexOutOfBoundsException*//


    (ll(0) :: x._1, x._2)
  } else {
    val y = mergeAndCountInv(ll, rl.tail)
    (rl(0) :: y._1, 1 + y._2)
  }
}

def sortAndCountInv(l: List[Int], n: Int): (List[Int], Int) = {
  if (n <= 1) (l, 0)
  else {
    val two_lists = l.splitAt(n / 2)
    val x = sortAndCountInv(two_lists._1, n / 2)
    val y = sortAndCountInv(two_lists._2, n / 2)
    val z = mergeAndCountInv(x._1, y._1)
    (z._1, x._2 + y._2 + z._2)
  }
}

val r = sortAndCountInv(il, il.length)
println(r._1.take(100))
r._2

}

4

2 回答 2

2

这种事情通常使用模式匹配更清楚地表达：

  def mergeAndCountInv(ll: List[Int], rl: List[Int]): (List[Int], Int) =
    (ll, rl) match {
      case (Nil, Nil) => (Nil, 0)

      case (Nil, _)   => (rl, 0)

      case (_, Nil)   => (ll, 0)

      case (ll0 :: moreL, rl0 :: moreR) =>
        if (ll0 <= rl0) {
          val x = mergeAndCountInv(moreL, rl)
          (ll0 :: x._1, x._2)
        }
        else {
          val y = mergeAndCountInv(ll, moreR)
          (rl0 :: y._1, 1 + y._2)
        }
    }
于 2013-01-31T04:30:11.263 回答
1

当您检查左侧或右侧或两个列表是否为空时，我建议使用elsein 。mergeAndCountInv因为不是返回，而是在计算中忽略一个元组。

于 2013-01-31T01:34:00.333 回答