ProductOfArrayExceptSelf [source code]
public class ProductOfArrayExceptSelf {
static
/******************************************************************************/
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right *= nums[i + 1];
res[i] *= right;
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
ProductOfArrayExceptSelf.Solution tester = new ProductOfArrayExceptSelf.Solution();
}
}
首先人逻辑想一下. 笨办法很简单, 不允许用除法, 那么我们对每一个entry做一次iterate, 跳过自己的iteration就行了, 这个最后的时间是N^2, 肯定是不行的. 我们要加速到N.
加速到O(N)有几个想法来的:
- bit
- pattern
- historical stream
- memo
想不起来, 完全不知道这个题目怎么写;
上面的算法也是直接根据答案写过来的, 速度是2ms (33%). 老题目了, 最优解很多, 尤其是这个题目discussion里面其实也就一个解法;
思考的时候大概想到了一点类似KMP的优化, 也就是让不同的index位置可以互相复用结果, 最后discussion看到的最优解就是这个做法;
Thank @lycjava3 for this smart solution. To understand it easily, let me explain it with an example.
Given numbers [2, 3, 4, 5], regarding the third number 4, the product of array except 4 is 235 which consists of two parts: left 23 and right 5. The product is leftright. We can get lefts and rights:
Numbers: 2 3 4 5
Lefts: 2 2*3 2*3*4
Rights: 3*4*5 4*5 5
Let’s fill the empty with 1:
Numbers: 2 3 4 5
Lefts: 1 2 2*3 2*3*4
Rights: 3*4*5 4*5 5 1
We can calculate lefts and rights in 2 loops. The time complexity is O(n).
We store lefts in result array. If we allocate a new array for rights. The space complexity is O(n). To make it O(1), we just need to store it in a variable which is right in @lycjava3’s code.
Clear code with comments:
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
// Calculate lefts and store in res.
int left = 1;
for (int i = 0; i < n; i++) {
if (i > 0)
left = left * nums[i - 1];
res[i] = left;
}
// Calculate rights and the product from the end of the array.
int right = 1;
for (int i = n - 1; i >= 0; i--) {
if (i < n - 1)
right = right * nums[i + 1];
res[i] *= right;
}
return res;
}
}
上面这个代码这个人自己改了一点, 原作者的代码:
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] res = new int[n];
res[0] = 1;
for (int i = 1; i < n; i++) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 1; i >= 0; i--) {
res[i] *= right;
right *= nums[i];
}
return res;
}
}
只能说这个算法真的很牛逼; 优化到O(1)space的几个套路我还是大概记得的(inplace input, inplace output, recursion, bit). 这一题, 优化到O(1)space其实不是难点, 难点是加速到O(N)time, 这个才是难点;
StackOverflow上面居然有帖子讨论过这个问题: https://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div
这个算法算是一个稍微利用了DP的memo的算法, 基本就是reuse previous entry的思路, 不过这个复用的具体做法细节还是真的非常聪明;
越看越觉得, 这个算法是真的6;
这个是下面的一个简化版本:
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size(),1);
for(int i=0,j=nums.size()-1, tmp1=1, tmp2=1;i<nums.size();++i,--j) {
res[i]*=tmp1, tmp1*=nums[i];
res[j]*=tmp2, tmp2*=nums[j];
}
return res;
}
};
其实这个代码挺丑的, 不过1pass的做法可以让你看到一个这个做法的过程; 另外这个改写过程本身并不是非常trivial, 他是看出来了这里的reuse其实只要两个var就行了; 同时left和right这两个, 分两个方向进行, 是不会互相影响的: 因为两个var本身互相独立, 然后res的每一个entry反正left和right都要乘, 顺序又无关, 所以只要保证乘了就行了; 可以学习一下, 不过感觉不是什么特别重要的东西;
这个算法本身是怎么想到的真的很难理解, 我尝试一下:
- 想要加速到O(N)时间, 那么思考用类似memo的技术, 尤其是直接reuse面前的entry;
- 乘积问题, 想到上面这个方向, 那么可能能够想到做一个product so far这样的array. (先不要去管space);
- 但是这个并不能直接解决这个问题. 想一想这样一个routine(like how you do reverse all the time in LinkedList problems)能够转化为我们当前题目需要的东西?
- 真正想要解释这里是怎么想到的就比较复杂了. 大概糊弄一点的说法可以说是人逻辑, 首先envision最后你需要的结果, 每一个entry得到的是什么, 比如是345, 245, 235, 345这样. 然后站在这里思考这个到底怎么理解怎样. 当然感觉这样一个解释好像还是不够其实;
- 想到一个正向一个反向组合一下就行了;
当然这个还是纸上谈兵, 不过还是希望对于理解有所帮助;
原作者的代码相对于解说员的的那个代码, 少用了一个temp, 这里有一个干脆一个temp都不用的:
public class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
res[0] = 1;
for(int i=1; i < nums.length; i++) {
res[i] = res[i-1] * nums[i-1];
}
for(int j = nums.length - 1; j > 0; j--) {
res[j] *= res[0];
res[0] *= nums[j];
}
return res;
}
}
具体的技巧还是一个InPlace, 不是没见过;
我们说过达到O(1)space的还有一个的技巧就是recursion, 结果这个题目还真有一个recursion的解法:
int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}
这个也是上面提到的那个StackOverflow的帖子里面的人写的. StackOverflow的大神还是多;
这个其实是一个非常高超的recursion算法.
看到一个看不懂的recursion算法, 我们常用的套路是:
- 看参数变化: what is the subproblem(尽管subproblem这个概念有时候本身就很难定义出来)
- 看参数使用: 参数是怎么被使用的
- 看返回值是什么;
这里的返回值的定义很清楚, 最后一行的return revProd, 以及第三行的revProd = multiply(...)这个其实都告诉你了, 这里的返回值是reverse product. 这个recursion复杂的地方也在于, 最后的recursive return value并不直接就是你的target value. 他这里是一个见过好几次的: side effect & recursive return value一起使用的套路. 真正需要返回的东西, 通过mutation, 直接存在a里面了.
另外注意他里面这个大If的使用, 其实这个就是一个base case的处理, 这里也可以写成:
if (indx >= N)
return 1;
不同的写法而已;
另外看看这个题目他是怎么想到转化成为一个recursion的: 这个题目的一个特点是需要一个正向的累积, 然后需要一个反向的累积过程. 这里反向的累积, 直接用recursion来做, 很方便. 而正向的累积, 其实很自然的, 用accum来做, 也很直白. 只能说这个人对于recursion的理解非常深. 这个题目本身跟recursion的关联于我个人来看, 其实不是那么明显的;
这个是1pass的另外一个写法, 其实差不多:
int[] result = new int[nums.length];
for (int i = 0; i < result.length; i++) result[i] = 1;
int left = 1, right = 1;
for (int i = 0, j = nums.length - 1; i < nums.length - 1; i++, j--) {
left *= nums[i];
right *= nums[j];
result[i + 1] *= left;
result[j - 1] *= right;
}
return result;
这个人下面还画了一堆解释, 画了一个矩阵什么的. 感觉没有必要, 这个1pass算法本身还是不难理解的, 就是那种常见的O(1) space DP里面的做法差不多, 本来要维护一个array, 实际上只要一个temp就够了; 然后prefix和suffix之间互相不干扰, 反向进行互相独立.
除了这个discussion好像就这么多解法了. 实际上, 好像这个题目就只有这一个解法? 就算是不考虑Follow-Up的O(1)space, 这个题目实际上也就只有这一个解法; 看起来很简单的一个题目, 实际上还是很刁钻;
Problem Description
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Difficulty:Medium
Total Accepted:103.8K
Total Submissions:212.2K
Contributor: LeetCode
Companies
amazon linkedin apple facebook microsoft
Related Topics
array
Similar Questions
Trapping Rain Water Maximum Product Subarray Paint House II