Product of Array Except Self

Leave a comment

October 30, 2016 by oneOokay

DP肯定不行O(n)就达不到。我能做到的只是两个for loop,初始化ans[i]都为1. 然后TLE了。O(n)的时间复杂度上来看,只能对array进行一次扫描。想不出其他的解法了。

for (int i = 0; i < nums.length; i ++) {
int tmp = nums[i];
for (int j = 0; j < nums.length; j ++) {
if (i == j) {
continue;}
ans[j] = ans[j] * nums[i];}}

http://fisherlei.blogspot.com/2015/10/leetcode-product-of-array-except-self.html

感觉也是不看答案不知道怎么写=。=

所以我的局限性在于:O(n)复杂度,并不意味着只能对array进行一次扫描。O(n)可以对array进行常数次的扫描。

一般这种题都可以分解成若干子问题来解决。
output[i] is equal to the product of all the elements of nums except nums[i].
简单的说 output[i] =  { i 前面的数的乘积}  X  { i 后面的数的乘积}

  • 3个array,一个ans, 一个product_before, 一个product_after.
  • 3个for loop: 一个从前至后扫,存nums[i]之前的所有元素的product;一个从后至前扫,存nums[i]之后的所有元素的product;最后一个forloop把product_before和product_after相乘得解。

WITHOUT EXTRA SPACE:

  • 第一次forloop 从前至后扫得到的ans[]为product_before[]
  • 第二次forloop: 从后至前扫,一个int value来存product_after value,ans[i] * product_after = ans[i];

public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int[] ans = new int[nums.length];
for (int i = 0; i < nums.length; i ++) {
if (i == 0) {
ans[i] = 1;
}else {
ans[i] = ans[i – 1] * nums[i – 1];
}
}
int product_after = 1;
for (int i = nums.length – 1; i >= 0; i –) {
if (i == nums.length – 1) {
ans[i] = product_after * ans[i];
}else {
product_after = product_after * nums[i + 1];
ans[i] = product_after * ans[i];
}}
return ans;
}}

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: