Paste_Image.png
My code:
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0)
return null;
int[] output = new int[nums.length];
output[0] = 1;
for (int i = 1; i < nums.length; i++)
output[i] = output[i - 1] * nums[i - 1];
int right = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {
output[i] *= right;
right *= nums[i];
}
return output;
}
public static void main(String[] args) {
Solution test = new Solution();
int[] a = {1, 2, 3, 4};
int[] b = test.productExceptSelf(a);
for (int i = 0; i < b.length; i++)
System.out.println(b[i]);
}
}
My test result:
这次题目我没做出来，因为实在想不出来有什么办法可以在O(n) 下完成，而且不用除法，甚至所用空间是常熟的，除了输出的数组。
网上查了才知道有个很巧妙地思想。
先用一个数组记录下，从左乘到右的乘积。
再用一个数组记录下，从右乘到左的乘积。
然后将两个数组相乘作为输出。
然后为了是空间变成常数级别。只用了一个数组。后期从右往左遍历时，直接把乘数和原来的从左往右保存下来的乘积相乘。一样的。
然后一些细节问题把握好就可以了。
**
总结： Array 这道题目的思想以前碰到过，从左往右遍历下，再从右往左遍历下，再合起来。可以避免平方级复杂度。
要留意了。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0)
return null;
int[] ret = new int[nums.length];
ret[0] = 1;
int mul = 1;
/** from left to right */
for (int i = 1; i < nums.length; i++) {
mul *= nums[i - 1];
ret[i] = mul;
}
/** from right to left */
mul = 1;
for (int i = nums.length - 2; i >= 0; i--) {
mul *= nums[i + 1];
ret[i] *= mul;
}
return ret;
}
}
这次做还是没有做出来。方法的确巧妙，我怎么就是想不到呢？我还依稀记得是分成两边乘，但就是忘了是这么处理的。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int n = nums.length;
int[] ret = new int[n];
ret[0] = 1;
for (int i = 1; i < n; i++) {
ret[i] = ret[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = n - 2; i >= 0; i--) {
right = right * nums[i + 1];
ret[i] = ret[i] * right;
}
return ret;
}
}
这道题目还是没想出来。主要考的就是这么个想法。
数组第i位记录的是 [o, i -1]的乘积。
然后再从右往左。就可以了。
Anyway, Good luck, Richardo! -- 09/02/2016
