构建乘积数组

算法 admin 215℃ 0评论

一个面试题:给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]A[i-1]*A[i+1]…*A[n-1]。不能使用除法。

分析:此题一看很简单,暴力破解肯定没问题,但时间复杂度会是O(n2), 题目限制不能用除法,显然普通方法无法直接达到O(n)

这里剑指OFFER给出一个巧妙的计算方法,构建一个乘积矩阵,利用已经计算过的部分求其它部分,从而节约时间复杂度

先计算下三角,再计算上三角,注意上三角是从下往上计算:

代码如下:

//构建乘积数组
function multiply($numbers)
{
    $len = count($numbers);
    if($numbers==null||$len<=1)return null;
    $b = array();

    $b[0]=1;
    for($i=1;$i<$len;$i++){
        $b[$i]=$b[$i-1]*$numbers[$i-1];
    }
    echo '<pre>';
    print_r($b);
    echo '</pre>';

    $temp = 1;
    for($j=$len-2; $j>=0; $j--){
        $temp *= $numbers[$j+1];
        $b[$j] *= $temp;  
    }

    return $b;
}

$a = [1, 2, 3, 4, 5];

echo '<pre>';
print_r(multiply($a));
echo '</pre>';

 

转载请注明:朋克网 » 构建乘积数组

喜欢 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址