ToB企服应用市场:ToB评测及商务社交产业平台
标题:
面试经典算法150题系列-除自身以外数组的乘积
[打印本页]
作者:
一给
时间:
2024-8-9 03:05
标题:
面试经典算法150题系列-除自身以外数组的乘积
除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer
等于 nums 中除 nums
之外其余各元素的乘积 。
标题数据
保证
数组 nums之中任意元素的全部前缀元素和后缀的乘积都在
32 位
整数范围内。
请
不要使用除法,
且在 O(n) 时间复杂度内完成此题。
示例 1:
<strong>输入:</strong> nums = [1,2,3,4]
<strong>输出:</strong> [24,12,8,6]
复制代码
示例 2:
<strong>输入:</strong> nums = [-1,1,0,-3,3]
<strong>输出:</strong> [0,0,9,0,0]
复制代码
实现思路:
这个题目可以通过预先盘算数组的前缀和后缀乘积来解决。由于不能使用除法,我们可以创建两个数组,一个用于存储每个元素之前全部元素的乘积(前缀乘积),另一个用于存储每个元素之后全部元素的乘积(后缀乘积)。然后,对于数组中的每个元素,我们可以将其对应的前缀乘积和后缀乘积相乘,得到除了该元素之外其他全部元素的乘积(
不知道前缀乘积和后缀乘积的朋友别畏惧,后面有补充
)。
实当代码:
// 这是一个公共方法,用于返回一个新数组,其中每个元素
// 是原数组中除了该元素之外其他所有元素的乘积。
public int[] productExceptSelf(int[] nums) {
// 获取输入数组的长度。
int length = nums.length;
// 初始化一个长度与输入数组相同的答案数组,初始值设为1。
int[] answer = new int[length];
// 初始化前缀乘积数组,所有元素初始值设为1。
int[] prefix = new int[length];
// 初始化后缀乘积数组,所有元素初始值也设为1。
int[] suffix = new int[length];
// 计算前缀乘积数组。
// 从第二个元素开始,每个元素是前一个元素与当前元素的乘积。
prefix[0] = 1;
for (int i = 1; i < length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
// 计算后缀乘积数组。
// 从最后一个元素开始,每个元素是后一个元素与当前元素的乘积。
suffix[length - 1] = 1;
for (int i = length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
// 计算答案数组。
// 对于每个索引i,答案数组的元素是前缀数组的元素与后缀数组的元素的乘积。
for (int i = 0; i < length; i++) {
answer[i] = prefix[i] * suffix[i];
}
// 返回计算好的答案数组。
return answer;
}
}
复制代码
好的,让我们通过一个具体的例子来演绎上述Java代码的执行过程。假设我们有以下输入数组:
int[] nums = {1, 2, 3, 4};
下面是代码执行的步调:
初始化数组
:
answer、prefix 和 suffix 数组都被初始化为长度与 nums 相同的数组,全部元素初始值为1。
盘算前缀乘积
(prefix 数组):
从索引1开始(因为索引0已经初始化为1),每个元素是前一个元素与 nums 中相应元素的乘积。
prefix[0] = 1,
prefix[1]=prefix[0] * nums[0]=1 * 1= 1,
prefix[2]=prefix[1] * nums[1]=1 * 2= 2,
prefix[3]=prefix[2] * nums[2]=2 * 3=6
复制代码
执行完循环后,prefix 数组为:[1, 1, 2, 6]
盘算后缀乘积
(suffix 数组):
从索引 length - 2 开始逆序遍历(因为索引 length - 1 已经初始化为1),每个元素是后一个元素与 nums 中相应元素的乘积。
suffix[3]=1,
suffix[2]=suffix[3]*nums[3] = 1 *4 =4,
suffix[1]=suffix[2]*nums[2] = 4 *3 =12,
suffix[0]=suffix[1]*nums[1] = 12 *2 =24
复制代码
执行完循环后,suffix 数组为:[24, 12, 4, 1]。
盘算答案数组
(answer 数组):
对于 nums 中的每个元素,answer 数组的元素是 prefix 数组与 suffix 数组对应元素的乘积。
以 nums[1] 为例,prefix[1] 是 1(因为 nums[0] 是1),suffix[1] 是 12,所以 answer[1] 是 1 * 12 = 12。
执行完循环后,answer 数组为:[24, 12, 8, 6]。
返回效果
:
answer 数组包含了输入数组 nums 中每个元素对应的乘积,不包含它们自己。
通过这个演绎过程,你们熟悉了吗?这个方法在
O(n)时间复杂度
内解决了题目,而且只使用了
O(n)的额外空间
。
知识补充:前缀数组(前缀乘积)与后缀数组(后缀乘积)
前缀数组和后缀数组的原理基于累积乘积的概念,它们用于快速盘算数组中元素的连续子集的乘积。下面是这两个概念的具体解释:
前缀数组(Prefix Array)
前缀数组是一个与原数组等长的数组,其中第 i 个元素包含从数组开始到第 i-1 个元素的乘积(如果存在的话)。换句话说,前缀数组的第 i 个元素是原数组从索引 0 到 i-1 的全部元素的乘积。
比方
: 假设有一个数组 nums = [a1, a2, a3, ..., an],前缀数组 prefix 将是这样的:
prefix[0] = 1(因为没有元素乘以 a1)
prefix[1] = a1
prefix[2] = a1 * a2
...
prefix
= a1 * a2 * ... * ai-1
后缀数组(Suffix Array)
与前缀数组相对应,后缀数组包含从数组末端开始到第 i+1 个元素的乘积。后缀数组的第 i 个元素是原数组从索引 i+1 到末端的全部元素的乘积。
比方
: 对于相同的数组 nums = [a1, a2, a3, ..., an],后缀数组 suffix 将是这样的:
suffix[n-1] = 1(因为没有元素乘以 an)
suffix[n-2] = an
suffix[n-3] = an * an-1
...
suffix
= an * an-1 * ... * ai+1
原理
前缀和后缀数组的原理基于这样一个究竟:对于数组中的任意元素 nums
,要盘算除了 nums
之外全部元素的乘积,可以将其前缀乘积(到 i-1 的乘积)和后缀乘积(从 i+1 到末端的乘积)相乘。这样,nums
项就不会出现在乘积中,因为它既不会被前缀也不会被后缀数组包含。
盘算示例
: 假设 nums = [3, 2, 4],我们有:
prefix = [1, 3, 6]
suffix = [8, 4, 1]
对于 nums[1](值为2),除了它之外的乘积是 prefix[1] * suffix[1] = 3 * 4 = 12。
这种方法的优势在于,它答应我们在O(1)时间内盘算出任意元素的非自身元素乘积,而不需要对数组举行多次遍历或使用除法。这在处理大数据集或需要避免除法操纵的场景中特别有用。
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4