每日一题|每日一题-238. 除自身以外数组的乘积

【每日一题|每日一题-238. 除自身以外数组的乘积】
每日一题-238. 除自身以外数组的乘积

  • 题目描述
  • 题目分析
  • 解决方案
  • 算法改良

题目描述
题目描述:
给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示:
题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
进阶:
你可以在常数空间复杂度内完成这个题目吗?( 出于对空间复杂度分析的目的,输出数组不被视为额外空间。)
来源:力扣(LeetCode)
题目分析 看到提示了没?出题者这几乎是明晃晃地把解法拍在脸上了,应该看出来这道题的算法了吧。
题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。
大体便是求数组的前缀连乘与后缀连乘,采用空间换时间的策略获得时间复杂度为O(n)的算法。
解决方案
class Solution { public: vector productExceptSelf(vector& nums) { vector bn; vector ans; int c,n,al=nums.size()-1; bn.resize(al); ans.resize(nums.size()); c=1; for(n=al; n>=0; --n) { c*=nums[n]; bn.push_back(c); } ans.push_back(bn[al-1]); c=nums[0]; for(n=1; n

算法改良 首先说一下这道题的暴力破解的解法。粗暴地叠两层循环,对于每一个数都重复地求其余项的连乘。
我们通过把求其余项连乘拆分为求前后缀子项连乘,本质上就是通过减少重复的乘法运算来降低时间复杂度。
因此,如果我们能再次减少乘法运算的次数,那么我们就能再进一步降低算法的时间复杂度。
首先,我们看一下求前后缀连乘的算法的过程。
设,输入数组nums为:[1,2,3,4],fn为前缀数组,bn为后缀数组,ans为求解答案。
nums 1 2 3 4
fn 1 1 * 2 1 * 2 * 3 /
bn 4 4 * 3 4 * 3 * 2 /
ans 4 * 3 * 2 4 * 3 * 1 4 * 1 * 2 1 * 2 * 3
通过观察,发现fn[3]和bn[3]的表达式十分相似,都是i * 2 * 3。其中,便存在2 * 3 这一个重复运算的乘法。那么,有解决方案来消除这一个重复的乘法运算吗?我们来探究一番。
既然2*3是重复的运算,那么我们能否先算2 * 3 再算1 * 2 * 3和2 * 3 * 4这两个算术表达式吗?似乎蕴含了动态规划的思想,该做法具有可行性。
每日一题|每日一题-238. 除自身以外数组的乘积
文章图片

我们成功的获得了1 * 2 * 3和2 * 3 * 4这两个表达式。这表示了我们完全可以先求其余项的任意子数组的连乘,再求其余项的连乘,而不局限于把其余项分解为前后缀子项求连乘。
因此,我们可以将数组分解到极致,每一个数为一个子数组,然后向上求其余项连乘。
这是我们的输入数组[1,2,3,4]
每日一题|每日一题-238. 除自身以外数组的乘积
文章图片

现在,被拆分为4个子数组:[ 1 ],[ 2 ],[ 3 ],[ 4 ]
每日一题|每日一题-238. 除自身以外数组的乘积
文章图片

然后,采用自底向上的动态规划思想,先求子数组的连乘,再求其余项的连乘。
每日一题|每日一题-238. 除自身以外数组的乘积
文章图片

最后,我们获得了题目需要的数组。
通过分析与计算,该算法的时间复杂度为O(log(n))
具体代码请各位读者自己实现。
————————————
2020/7/3 更正:
根据乘积次数计算时间复杂度,采用动态规划的时间复杂度为O(n+log(n)),但是前后缀的时间复杂度为O(2n),因此该算法是对原算法的改良。
每个数组的成员至少需要计算一次,因此不太可能存在时间复杂度为O(log(n))的算法。

    推荐阅读