面试题66：构建乘积数组

把每个排除自身的乘积拆成左侧前缀积与右侧后缀积，用两次方向相反的扫描在不除法条件下构建结果。

学习目标

  • 能把排除自身的乘积拆成前缀积与后缀积，两次方向相反扫描构建
  • 能解释"不能使用除法"的原因（含零时无法恢复）
  • 能处理长度为 0 和 1 的边界

从“总积除以自己”为何不被允许开始

输入A为1、2、3、4、5时，所有元素总积120，看似可以用120除以A中每一项得到B。但题目明确“不能使用除法”，而且输入含0时总积变为0，零位置需要的“其余元素积”无法通过0除以0恢复。

“构建乘积数组”要求每个B[i]等于除A[i]之外所有输入元素的乘积：

Bi=∏0≤j<nj≠iAjB_i=\prod_{\substack{0\le j\lt n\\j\ne i}}A_j

不使用除法意味着不能先把被排除项乘进去再尝试逆操作。应从一开始就只乘索引i左边和右边的元素。

先预测输入1、2、0、4、5的结果：只有零所在的B[2]不乘这个0，可以得到1乘2乘4乘5等于40；其余每个输出都会包含A[2]的0，所以为0。

把排除自身拆成与

对于位置i，所有被保留元素天然分成A[0]到A[i-1]与A[i+1]到A[n-1]。把左段乘积记为L_i、右段乘积记为R_i，则B_i等于两者相乘。

Li=∏j=0i−1Aj,Ri=∏j=i+1n−1Aj,Bi=LiRiL_i=\prod_{j=0}^{i-1}A_j, \qquad R_i=\prod_{j=i+1}^{n-1}A_j, \qquad B_i=L_iR_i

当某一侧没有元素时，乘法单位元是1。这个定义让边界无需特殊公式：L0=1L_0=1，Rn−1=1R_{n-1}=1。

矩阵图中每行对应一个B，主对角线A[i]被排除；对角线左下方是左侧因子，右上方是右侧因子。这就是原章的“下三角连乘与上三角连乘”。

分步1 / 3

第一遍：前缀积

B[i] 等于 A[0] 到 A[i-1] 的乘积。

前缀积扫描（从左到右）A[0]B[0] = 前缀0A[1]B[1] = 前缀1A[2]B[2] = 前缀2A[3]B[3] = 前缀3A[4]B[4] = 前缀4后缀积扫描（从右到左）A[0]A[1]A[2]A[3]A[4]
前缀积从左到右，后缀积从右到左，两次扫描构建乘积数组

第一遍写入

L_i可从左到右递推。先把output[0]设为1；对每个i从1开始，output[i]等于output[i-1]乘A[i-1]。

L0=1,Li=Li−1Ai−1(1≤i<n)L_0=1, \qquad L_i=L_{i-1}A_{i-1} \quad(1\le i\lt n)

输入1、2、3、4、5经过第一遍后，output是1、1、2、6、24。此时它还不是最终B，只保存每个位置左边的乘积。

这一步不会读output中尚未写入的位置，也不需要额外前缀数组；结果容器本身就是中间存储。

第二遍把乘回结果

从右到左递推。作者不再申请一整个R数组，只用temp维护当前右侧累计积；每向左移动一格，先把A[i+1]乘入temp，再将temp乘入output[i]。

Rn−1=1,Ri=Ai+1Ri+1,Bi←BiRiR_{n-1}=1, \qquad R_i=A_{i+1}R_{i+1}, \qquad B_i\leftarrow B_iR_i

这种只用一个变量保存当前右积的方式称为。末项B[n-1]在第一遍已经是全部左积，右侧为空积1，所以第二遍从n-2开始。

两遍合起来就是“前缀积与后缀积”：第一遍填下三角连乘，第二遍用temp填上三角连乘，最终每行恰好跳过对角元素。

忠实还原作者函数

作者输入和输出都是双精度vector引用。调用者必须预先创建与输入等长的output；只有长度相等且大于1时函数才写结果，否则静默保持output原值。

void BuildProductionArray(
    const std::vector<double>& input,
    std::vector<double>& output) {
    int inputLength =
        static_cast<int>(input.size());
    int outputLength =
        static_cast<int>(output.size());
 
    if (inputLength == outputLength &&
        outputLength > 1) {
        output[0] = 1;
        for (int i = 1;
             i < inputLength;
             ++i) {
            output[i] =
                output[i - 1]
              * input[i - 1];
        }
 
        double temp = 1;
        for (int i = inputLength - 2;
             i >= 0;
             --i) {
            temp *= input[i + 1];
            output[i] *= temp;
        }
    }
}

函数名写作Production而不是Product，是作者源码命名；算法仍然构建乘积数组。时间O(n)，除输出数组外额外空间O(1)。若把输出本身计入总空间，则为O(n)，因为题目本来就要求返回n个结果。

作者把size_t长度缩窄为int，超大vector可能失真；正常面试规模无碍。更重要的是input和output不能是同一个vector：第一遍写output会同时改掉后续还要读取的input，破坏算法。源码没有检测这种别名。

作者长度契约与数学边界

长度不一致时作者不返回错误，也不调整output；长度0或1即使相等，也因为大于1条件不成立而不写。官方最短输入是两个元素。

数学上，空输入自然返回空数组；单元素输入的B[0]排除唯一元素后是空积1。现代API可以直接返回新容器，从而明确支持这两个边界并消除预分配、长度不匹配与输入输出别名问题。

#include <cstddef>
#include <vector>
 
std::vector<long double>
constructProductArray(
    const std::vector<long double>& input) {
    const std::size_t n = input.size();
    if (n == 0)
        return {};
 
    std::vector<long double> output(n, 1.0L);
 
    for (std::size_t i = 1;
         i < n;
         ++i) {
        output[i] =
            output[i - 1] * input[i - 1];
    }
 
    long double suffix = 1.0L;
    for (std::size_t i = n - 1;
         i > 0;
         --i) {
        suffix *= input[i];
        output[i - 1] *= suffix;
    }
 
    return output;
}

无符号下标反向循环容易写错。上面让i表示尚未乘入的右侧元素下标，从n-1递减到1，每轮更新output[i-1]，避免size_t减到0后继续回绕。n等于1时循环不进入，output保持1。

无需任何特殊分支

双扫描从未计算总积，也从未除以A[i]，所以零会自然传播：

一个零时，只有零位置的左右两段都不包含零，得到其余元素乘积；其他位置至少一侧包含零。两个或更多零时，排除任何单一位置后仍至少保留一个零，所有结果为0。

负数同样无需特殊逻辑。每个B的符号由“除自身外负数个数”的奇偶性决定，两遍普通乘法自然得到作者Test4的120、-60、40、-30、24。

的正确性

第一遍结束后，可用归纳证明output[i]等于A[0]到A[i-1]的乘积：i等于0是空积1；若i-1成立，再乘A[i-1]就得到i的左积。

第二遍从右向左时，temp在乘入A[i+1]后等于A[i+1]到A[n-1]的乘积。output[i]原本是左积，乘temp后恰好得到排除A[i]的全部因子。两个不变式共同证明每个位置正确。

这里的不是额外数据结构，而是一种理解两遍扫描为何没有漏乘或重复乘的图形化方法。

整个算法读取每个输入元素至多两次，写每个输出有限次，时间线性；相比每个i重新扫描其余n-1项的O(n平方)暴力法，复用了相邻位置共有的前后缀信息。

空间复用成立的关键不是“没有中间状态”，而是两个阶段需要的状态方向互补：反向扫描开始时，output[i]中的前缀积已经定稿，后续只会再乘一次右积；temp则只代表当前边界右侧的原始输入乘积。只要输入保持只读，覆盖output不会影响尚未计算的位置。这个读写依赖也解释了为什么独立输出容器可行、输入输出别名却会失败。面试中应把这条依赖说清，而不只是背诵O(1)额外空间。

浮点与整数乘积边界

作者用double并在测试中以绝对误差1e-7比较。乘法顺序不同会产生浮点舍入差异；绝对容差对极大或极小量未必合理，工程测试通常结合相对误差。

改用long long只改变范围，不消除溢出；乘积增长很快。整数业务需要约束输入、检测乘法溢出或使用大整数。浮点业务还要考虑正负零、无穷、NaN和上溢下溢。

“不能使用除法”也避免了浮点总积除自身可能放大舍入误差，但前后缀乘积仍会因结合顺序不同产生微小差异。结果精度契约应独立于算法复杂度说明。

五组官方测试与测试代码问题

作者准备五组输入：无零、一个零、两个零、两个负数，以及长度2。期望分别检查普通结果、零传播、符号和最小有效长度。

原测试函数把output声明为非常量左值引用，却在调用时直接传临时vector；还用char指针接收字符串字面量。现代标准C++不能把临时量绑定到非常量左值引用，字符串字面量也不应转成char指针，因此测试外壳依赖旧编译器扩展。核心BuildProductionArray算法不受这个语法问题影响。

现代测试应创建命名output变量，或直接测试返回vector的新接口。暴力预言机对每个i单独乘所有j不等于i的元素，虽然O(n平方)，但逻辑独立，适合随机短数组对拍。

#include <cassert>
#include <vector>
 
std::vector<long double> bruteProduct(
    const std::vector<long double>& input) {
    std::vector<long double> output(
        input.size(), 1.0L);
    for (std::size_t i = 0;
         i < input.size();
         ++i) {
        for (std::size_t j = 0;
             j < input.size();
             ++j) {
            if (i != j)
                output[i] *= input[j];
        }
    }
    return output;
}
 
void testProductArray() {
    assert(constructProductArray({}).empty());
    assert(constructProductArray({7}) ==
           std::vector<long double>{1});
    assert(constructProductArray(
        {1, 2, 0, 4, 5}) ==
        std::vector<long double>{
            0, 0, 40, 0, 0});
    assert(constructProductArray(
        {1, 2, 0, 4, 0}) ==
        std::vector<long double>{
            0, 0, 0, 0, 0});
}

浮点随机对拍应使用容差而非vector精确相等；上述小整数可精确表示，直接比较是安全的。还要测试作者旧接口在长度不匹配时保持output不变，以锁定其实际契约。

本章练习

练习

问题 1： 为什么不能用除法？

问题 2： 前缀积和后缀积如何计算？

问题 3： 长度为 1 的数组返回什么？

本章回顾

  1. 构建乘积数组要求B[i]等于除A[i]外全部元素乘积，不能使用除法。
  2. 每一行可拆为下三角连乘与上三角连乘，也就是前缀积与后缀积。
  3. 空积定义为1，使首项左积、末项右积和单元素结果统一。
  4. 第一遍从左写前缀，第二遍从右用temp滚动后缀并乘回output。
  5. 两遍时间O(n)，除输出外额外空间O(1)。
  6. 零和负数无需特殊分支；一个零只有其位置可能非零，两个零使结果全零。
  7. 作者要求output预分配、等长且长度大于1，长度不符时静默不写。
  8. 输入输出别名会破坏算法，现代返回值接口可消除这类契约风险。
  9. 作者五组测试逻辑完整，但临时vector绑定非常量引用依赖旧编译器扩展。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

构建乘积数组
每个元素等于除自身外所有元素乘积。
前缀积
当前元素左侧所有元素的乘积。
后缀积
当前元素右侧所有元素的乘积。
零处理
含零时无需特殊分支，前缀×后缀自动处理。
上下三角
前缀积对应下三角矩阵，后缀积对应上三角矩阵。
复习本章（5 题）

讨论

评论区加载中…