Product of Array Except Self

Leave a comment

October 30, 2016 by oneOokay

O(N)就是扫常数遍array即可.

except self这个问题,考虑乘法的特殊性,随便置换乘,以及先求部分的乘积之类blabla,就可以分割成前后两部分.以后注意有关except self的问题,试着分割问题成前后两部分来考虑是否可解.

可以第一遍从头扫同时initiate before和after array. 也可以第一遍从头扫initiate before array,第二遍从尾扫,一边计算after array一边得出answer array.

i [0, length – 1]
before[i] = before[i – 1] * nums[i – 1];
after[len – i – 1] = after[len – i] * nums[len – i];


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

所以我的局限性在于: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];

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: