238. Product of Array Except Self.md

238. Product of Array Except Self

Question

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note:

• The linked list will have at least two elements.
• All of the nodes' values will be unique.
• The given node will not be the tail and it will always be a valid node of the linked list.
• Do not return anything from your function.

Thinking:

• Method 1:
  • 先存储左侧的乘积。
  • 再存储右侧的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] result = new int[len];
        for(int i = 0, temp = 1; i < len; i++){
            result[i] = temp;
            temp *= nums[i];
        }
        for(int i = len - 1, temp = 1; i >= 0; i--){
            result[i] *= temp;
            temp *= nums[i];
        }
        return result;
    }
}

二刷

• Method 1:
  1. We use a same size array to save the production of left side(exclude itself).
  2. Then we traverse the array from end to top and time the values saved in the array to save the product of right side.
  3. For each number, we actually times the left product with right product(itself is not included).

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] result = new int[len];
        for(int i = 0, temp = 1; i < len; i++){
            result[i] = temp;
            temp *= nums[i];
        }
        for(int i = len - 1, temp = 1; i >= 0; i--){
            result[i] *= temp;
            temp *= nums[i];
        }
        return result;
    }
}

Third Time

• Method 1: O(N) time complexity and O(1) space complexity

   class Solution {
       public int[] productExceptSelf(int[] nums) {
           int[] left = new int[nums.length];
           left[0] = 1;
           for(int i = 1; i < nums.length; i++){
               left[i] = left[i - 1] * nums[i - 1];
           }
           int right = 1;
           for(int i = nums.length - 2; i >= 0; i--){
               right *= nums[i + 1];
               left[i] *= right;
           }
           return left;
       }
   }