Leetcode Answers 238

今晚的最后一题,是求数组乘积的问题,而且是刚好在九章上看过的问题。

题目:
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.)

思路:
这里首先考虑一个问题,就是output[i]除了分解成product / nums[i]以外还能分解成什么形式?很简单:nums[0] nums[1] … nums[i-1] nums[i+1] … * nums[n-1]。那么这里就可以拆成两半,一半是prefix,nums[0]..nums[i-1],另一半是suffix,nums[i+1]…nums[n-1]。再想一想,当我正向遍历的时候,我就可以让output的每一项等于其prefix,再反向遍历乘上suffix,是不是问题就解决了?是的。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int[] ProductExceptSelf(int[] nums) {
var output = new int[nums.Length];
var fp = 1;
output[0] = fp;
for(int i = 1; i < nums.Length; ++i){
fp *= nums[i-1];
output[i] = fp;
}
fp = 1;
for(int i = nums.Length - 2; i >= 0; --i){
fp *= nums[i+1];
output[i]*=fp;
}
return output;
}
}

考察:这个正向-反向遍历方法应该很有用,所以要牢记。

以上。

17-04-25
@Sturbridge