Product of Array Except Self

Product of Array Except Self

问题：

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.)

思路：

　　一个负责从左到右，一个负责从右到左

代码：

public class Solution {
public int[] productExceptSelf(int[] nums) {
    int[] res = new int[nums.length];
    System.arraycopy(nums, 0, res, 0, nums.length);
    for (int i = 1; i < nums.length; i++) {
        nums[i] = nums[i] * nums[i-1];
    }
    for (int i = res.length - 2; i >= 0; i--) {
        res[i] = res[i] * res[i+1];
    }
    for (int i = 0; i < nums.length; i++) {
        if (i == 0) {res[i] = res[i+1];}
        else if (i == nums.length - 1) {res[i] = nums[i-1];}
        else {res[i] = nums[i-1] * res[i+1];}
    }
    return res;
}
}

View Code

学习之处：

• 这个代码不会写，果然好久没写代码了，思路也有点凝固了。
• 这道题感受最深的是，对于数组问题可以一分为二的进行看待，从左边看，从右边看，从左右不同的角度看
• 对于数组的除了的问题，或者是要划分的问题，或者是没有思路的问题，考虑一下先从左往右，再从右往左，或者左右同时进行，也许就会柳暗花明。

原文：http://www.cnblogs.com/sunshisonghit/p/4674169.html