P142 除了自身元素的数组乘积

描述#

这个题目说的是，给你一个大小为 n 的整数数组 nums，其中 n > 1。你要返回一个数组 output。其中，output(i) 是原数组中除了 nums(i) 以外，所有数字的乘积。注意，这道题目的求解过程不能使用除法。

比如说，给你的数组是：
1, 4, 2, 8
你要返回的数组就是：
64, 16, 32, 8
可以看到返回的数组中，每个位置上的数字都是原数组中除了那个位置以外的所有数字乘积。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] leftProduct = new int[n];
    int[] rightProduct = new int[n];
    int[] output = new int[n];
    leftProduct[0] = nums[0]; rightProduct[n-1] = nums[n-1];

    for (int i = 1; i < n; ++i)
      leftProduct[i] = leftProduct[i-1] * nums[i];
    for (int j = n-2; j >= 0; --j)
      rightProduct[j] = rightProduct[j+1] * nums[j];

    output[0] = rightProduct[1]; output[n-1] = leftProduct[n-2];
    for (int i = 1; i < n-1; ++i)
      output[i] = leftProduct[i-1] * rightProduct[i+1];
    return output;
  }

  // Time: O(n), Space: O(1)
  public int[] productExceptSelfO1(int[] nums) {
    int n = nums.length;
    int[] output = new int[n];
    output[n-1] = nums[n-1];

    for (int j = n-2; j >= 0; --j)
      output[j] = output[j+1] * nums[j];
    for (int i = 1; i < n; ++i)
      nums[i] = nums[i-1] * nums[i];

    int first = output[1], last = nums[n-2];
    for (int i = 1; i < n-1; ++i)
      output[i] = nums[i-1] * output[i+1];
    output[0] = first; output[n-1] = last;
    return output;
  }

  // Time: O(n), Space: O(1)
  public int[] productExceptSelfNotChangeInputO1(int[] nums) {
    int n = nums.length;
    int[] output = new int[n];
    output[0] = 1;
    for (int i = 1; i < n; ++i)
      output[i] = output[i-1] * nums[i-1];

    int right = 1;
    for (int i = n-1; i >= 0; --i) {
      output[i] *= right;
      right *= nums[i];
    }
    return output;
  }

}