一千萬個為什麽

搜索

在scala中以遞歸方式查找列表中的最大值

我是斯卡拉新手,有更好的方法可以用最基本的知識來表達這一點嗎?

 def findMax(xs: List[Int]): Int = {
      xs match {
        case x :: tail => (if (tail.length==0) x else (if(x>findMax(tail)) x else (findMax(tail))))
      }
    }

最佳答案

你在這裏有兩個問題。首先,您調用 tail.length 這是一個操作order (N),所以在最壞的情況下,這會花費你N * N個步驟,其中N是長度的序列。第二個是你的函數不是尾遞歸的 - 你將 findMax 從外部調用到內部。

編寫正確的遞歸函數的通常策略是

  • 考慮每個可能的模式情況:這裏有空列表 Nil 或非空列表 head :: tail 。這解決了您的第一個問題。
  • 攜帶臨時結果(這裏是當前最大值的猜測)作為函數的另一個參數。這解決了你的第二個問題。

這給出:

import scala.annotation.tailrec

@tailrec
def findMax(xs: List[Int], max: Int): Int = xs match {
  case head :: tail => findMax(tail, if (head > max) head else max)
  case Nil => max
}

val z = util.Random.shuffle(1 to 100 toList)
assert(findMax(z, Int.MinValue) == 100)

如果你不想公開這個額外的參數,你可以寫一個輔助的內部函數。

def findMax(xs: List[Int]): Int = {
  @tailrec
  def loop(ys: List[Int], max: Int): Int = ys match {
    case head :: tail => loop(tail, if (head > max) head else max)
    case Nil => max
  }
  loop(xs, Int.MinValue)
}

val z = util.Random.shuffle(1 to 100 toList)
assert(findMax(z) == 100)

為了簡單起見,如果列表為空,我們返回 Int.MinValue 。更好的解決方案可能是為這種情況拋出異常。


這裏的 @tailrec 註釋是可選的,它只是保證我們確實定義了一個尾遞歸函數。這樣做的好處是,如果列表非常長,我們不能產生堆棧溢出。

轉載註明原文: 在scala中以遞歸方式查找列表中的最大值