构建乘积数组1

题目要求在给定一个数组 A 之后，构建一个新的数组 B，使得 B[i] 等于数组 A 中所有不包括下标为 i 的元素的乘积。换句话说，B[i] 是 A 中除去 A[i] 之后剩余元素的乘积。题目强调不能使用除法，并给出了两个不同的解法。 我们看第一个解法。这个解法使用了额外的一个临时数组 `tmp`，在每次循环中，将原数组 A 的一个元素删除（`tmp.erase(tmp.begin()+i)`），然后计算剩下的元素的乘积（`cur*=tmp[j]`），最后将结果存入结果数组 `res` 中。这种方法虽然直观，但效率较低，因为它需要多次遍历数组并进行元素删除操作，这会导致超时。 第二个解法更加高效，它使用了两个遍历来计算数组 B。初始化一个大小与数组 A 相同的新数组 B，所有元素初始值为 1。然后，从第二个元素（下标为 1）开始，将前一个元素的值（下标为 i-1）乘以当前元素的值（下标为 i），累加到 B[i] 上。这样，遍历完成后，数组 B 的前半部分已经包含了从第二个元素到倒数第二个元素的所有不相邻元素的乘积。 接下来，从最后一个元素（下标为 n-1）向前遍历，利用一个变量 `accu` 来存储从当前元素到末尾的元素乘积。在每个步骤中，`accu` 乘以下一个元素的值，然后更新 B[i] 为 B[i] 与 `accu` 的乘积。这样，遍历结束后，数组 B 的后半部分也包含了从第一个元素到倒数第二个元素的所有不相邻元素的乘积。 综合这两个遍历，数组 B 就包含了所有需要的乘积，且没有使用除法。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)，比第一个解法更优。 总结知识点： 1. 题目类型：数组处理，LeetCode 题目。 2. 问题核心：构建新的数组 B，其中 B[i] 是数组 A 中去掉 A[i] 后其他元素的乘积。 3. 解决策略：不使用除法，通过两个遍历计算数组 B。 4. 第一个解法：创建临时数组，删除元素并计算乘积，时间复杂度高。 5. 第二个解法：从两端同时计算，先处理前半部分，再处理后半部分，时间复杂度和空间复杂度均为线性。 6. 遍历技巧：使用累积乘积变量（如 `accu`），避免重复计算。 7. 优化思路：避免不必要的元素删除和重复遍历，以提高算法效率。