html代码在线提取_什么网页游戏最火_整合营销网络推广_西安百度推广竞价托管

LCR191

题目描述

给定一个数组 arrayA，返回一个数组 arrayB，其中 arrayB[i] 是 arrayA 中除了 arrayA[i] 之外所有元素的乘积。

注意：

不能使用除法。
时间复杂度为 O(n)，空间复杂度为 O(1)（输出数组不计入空间复杂度）。

示例

示例 1

输入:

arrayA = [1, 2, 3, 4]

输出:

[24, 12, 8, 6]

解释:

arrayB[0] = 2 * 3 * 4 = 24
arrayB[1] = 1 * 3 * 4 = 12
arrayB[2] = 1 * 2 * 4 = 8
arrayB[3] = 1 * 2 * 3 = 6

示例 2

输入:

arrayA = [0, 1, 2, 3]

输出:

[6, 0, 0, 0]

解释:

arrayB[0] = 1 * 2 * 3 = 6
arrayB[1] = 0 * 2 * 3 = 0
arrayB[2] = 0 * 1 * 3 = 0
arrayB[3] = 0 * 1 * 2 = 0

思路分析

问题核心

我们需要计算数组中每个元素左边所有元素的乘积和右边所有元素的乘积，然后将两者相乘得到结果。

思路拆解

初始化数组：
- 使用两个辅助数组 left 和 right，分别存储每个元素左边和右边所有元素的乘积。
计算左边乘积：
- 从左到右遍历数组，计算每个元素左边所有元素的乘积。
计算右边乘积：
- 从右到左遍历数组，计算每个元素右边所有元素的乘积。
计算结果：
- 将 left 和 right 数组对应位置的值相乘，得到最终结果。

代码段

class Solution {public int[] statisticalResult(int[] arrayA) {if (arrayA.length == 0) {return new int[0];}int len = arrayA.length;int[] arrayB = new int[len];int[] left = new int[len];int[] right = new int[len];left[0] = 1;for (int i = 1; i < len; i++) {left[i] = left[i - 1] * arrayA[i - 1];}right[len - 1] = 1;for (int i = len - 2; i >= 0; i--) {right[i] = right[i + 1] * arrayA[i + 1];}for (int i = 0; i < len; i++) {arrayB[i] = left[i] * right[i];}return arrayB;}
}

在这里插入图片描述

代码逐行讲解

空数组处理：
```
if (arrayA.length == 0) {return new int[0];
}
```
- 如果输入数组为空，则返回空数组。

初始化变量：

int len = arrayA.length;
int[] arrayB = new int[len];
int[] left = new int[len];
int[] right = new int[len];

获取数组长度，并初始化结果数组 arrayB 和辅助数组 left、right。

计算左边乘积：

left[0] = 1;
for (int i = 1; i < len; i++) {left[i] = left[i - 1] * arrayA[i - 1];
}

从左到右遍历数组，计算每个元素左边所有元素的乘积。

计算右边乘积：

right[len - 1] = 1;
for (int i = len - 2; i >= 0; i--) {right[i] = right[i + 1] * arrayA[i + 1];
}

从右到左遍历数组，计算每个元素右边所有元素的乘积。

计算结果：
```
for (int i = 0; i < len; i++) {arrayB[i] = left[i] * right[i];
}
```
- 将 left 和 right 数组对应位置的值相乘，得到最终结果。
返回结果：
```
return arrayB;
```
- 返回结果数组 arrayB。

复杂度分析

时间复杂度

遍历数组三次，时间复杂度为 O(n)。

空间复杂度

使用了两个辅助数组 left 和 right，空间复杂度为 O(n)。

总结的知识点

辅助数组：
- 使用辅助数组存储中间结果，简化计算。
遍历数组：
- 通过遍历数组计算左边和右边的乘积。
乘积计算：
- 将左边和右边的乘积相乘，得到最终结果。

整合

class Solution {public int[] statisticalResult(int[] arrayA) {if (arrayA.length == 0) {return new int[0];}int len = arrayA.length;int[] arrayB = new int[len];int[] left = new int[len];int[] right = new int[len];left[0] = 1;for (int i = 1; i < len; i++) {left[i] = left[i - 1] * arrayA[i - 1];}right[len - 1] = 1;for (int i = len - 2; i >= 0; i--) {right[i] = right[i + 1] * arrayA[i + 1];}for (int i = 0; i < len; i++) {arrayB[i] = left[i] * right[i];}return arrayB;}
}

总结

通过辅助数组和遍历，能够高效地计算数组中每个元素左边和右边所有元素的乘积，并得到最终结果。