• Personal blog: Javaniuniu.com/
  • Difficulty:medium
  • The problem involves the algorithm:
  • Ideas:Product = product of the left * product of the right
  • Similar questions:

The title238. Product of arrays other than itself

You are given an array of integers of length n, nums, where n > 1 returns output, where output[I] is equal to the product of all elements in nums except nums[I].

Example:

Input: [1,2,3,4] output: [24,12,8,6]Copy the code

Tip: The problem data ensures that the product of all prefixes and suffixes (or even the entire array) of any element in the array is within the range of 32-bit integers.

Note: Please do not use division and complete this problem in O(n) time complexity.

Advanced: Can you do this problem in constant space complexity? (For the sake of spatial complexity analysis, the output array is not considered extra space.)

Method 1 product = product of the left * product of the right

  • Answer:

    • First impression, if I want to divide,
      (Product of all numbers / n u m s [ i ] ) (Product of all numbers /nums[I])       , and need to be right0Do judgment;
    • Second impression, I want to try sliding Windows, but it’s going to be n2n^2n2;
    • Along the idea of sliding Windows, improvedProduct = product to the left of current number * product to the right of current number

  • Complexity analysis:

    • Time complexity: O(n)O(n)O(n), where NNN represents the length of the array
    • Space complexity: O(1)O(1)O(1), excluding returned array space is NNN

java

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length]; // Initialize the array with length nums.length
        int r = 1; // The product of the right-hand side
        for(int i=nums.length-1; i>=0; i--) { r *= nums[i]; res[i] = r; }int l = 1; // The product on the left
        for(int i = 0; i<nums.length-1; i++) { res[i] = l * res[i+1];
            l *= nums[i];
        }
        res[nums.length-1] = l;
        returnres; }}Copy the code

python

class Solution(object) :
    def productExceptSelf(self, nums) :
        res = [1] * len(nums) Initialize an array of length le(nums)
        r = 1 # the product of the right-hand side
        for i in range(len(nums)-1, -1, -1):
            r *= nums[i]
            res[i] = r

        l = 1 The product of the left-hand side
        for i in range(len(nums)-1):
            res[i] = res[i+1] * l
            l *= nums[i]
        res[-1] = l
        return res
Copy the code