时间戳

首页 > 解决方案 > 带有尾递归的除 Self 之外的数组的乘积

scala - 带有尾递归的除 Self 之外的数组的乘积

问题描述

我想知道是否可以使用尾递归重写以下函数，并且在这种情况下使用递归对时间/空间复杂度有帮助吗？，下面是我在没有尾递归的情况下尝试过的

input:[4,2,4,6]
output:[48,96,48,32]

  def productExceptSelf(nums: Array[Int]): Array[Int]={
    val len = nums.length

    val output_arr= new Array[Int](len)

    output_arr(0)=1
    for(i<- 1 to len-1)
    {
      output_arr(i) = nums(i-1) * output_arr(i-1)
    }

    var R =1
    var j=len-1
    while(j>=0)
    {
      output_arr(j) =  output_arr(j)* R
      R = R * nums(j)
      j-=1
    }

    output_arr
  }

标签： scala

解决方案

不确定您希望如何使用尾递归来编写它，但最简单的方法是这样的：
PS：我正在使用ArraySeq这是一个不可变数组（在 上介绍2.13），请随意继续使用普通数组。

def productExceptSelf(nums: ArraySeq[Int]): ArraySeq[Int] = {
  val totalProduct = nums.product

  nums.map(x => totalProduct / x)
}

不使用除法的解决方案。

def productExceptSelf(nums: ArraySew[Int]) : ArraySeq[Int] =
  ArraySeq.tabulate(nums.length) { i =>
    nums.foldLeft(1 -> 0) { case ((acc, j), x) =>
      val newAcc = if (i == j) acc else acc * x
      newAcc -> (j + 1)
    }._1
  }

推荐阅读