This is the 20th day of my participation in the August Text Challenge.More challenges in August

Product of arrays other than themselves (Item Number 238)

The title

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 ** title 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.

** Instructions: 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.)

link

Leetcode-cn.com/problems/pr…

explain

This one, this is the DP variant.

To be honest, at the first sight of this problem, I felt that I could solve it with a two-layer cycle.

The inner loop computes the entire array except for the product of the current number. In JavaScript we can use reduce to simplify the code, but this time complexity is O(n * n).

It turns out that this really doesn’t work for AC, because there’s a huge array at the back of the test case to make you time out.

So what else is there to do? After thinking about it for 10 minutes, DP solved the problem.

Dp [I][j] can represent the product of all digits in an array from I to j, so it is easy to find a product of all digits except one, for example:

[1.2.3.4]
Copy the code

For example, if we take the product of 2 other numbers in this position, whose index is 1, then assuming we already have the DP array, the product of the current position is:

dp[0] [0] * dp[2] [3]
Copy the code

Dp [0][0] stands for 1, dp[2][3] stands for 3 * 4, two times one is 1 * 3 * 4, which is the result we need.

So how do I get this DP array? So before we do that we need to know what the DP array should contain.

Because if it was a normal DP array, the way to get the array would be two for loops, which would be O(n * n), which is beyond the requirements of the problem, so we need to simplify the DP array.

Back to the question, right? What kind of data does this DP array need to provide us?

Because it’s all done from start to finish, it only needs to have two layers:

  • The first layer represents the product from the first element of the array to the position of each element

    So dp[I] is the product of all the numbers from 0 to position I

  • The second layer represents the product from the last element of the array to the position of each element

    That is, dp[I] represents the product of all numbers from nums. length-1 to I, which is the first layer of data in reverse

We can loop through the array twice, dividing the DP array by two layers, or loop through the DP array by one layer. We can use nums.length and I to evaluate the two layers in a for loop.

Once you get the value, go through each element to get the final result.

Own answer (doubleforLoop)

var productExceptSelf = function(nums) {
  const len = nums.length
  const res = new Array(len)
  for (let i = 0; i < len; i++) {
    res[i] = nums.reduce((total, num, index) = > {
      if (index === i) return total
      return total * num
    }, 1)}return res
};
Copy the code

The code is simple, just a double-layer for loop, and it simply fails, falling over 19/20 test cases.

Your own answer (DP+ even)

This is the method in the explanation 👇 :

var productExceptSelf = function(nums) {
  const len = nums.length
  const dp = Array.from({length: 2}, () = > new Array())
  const res = new Array(len)
  dp[0] [0] = 1
  dp[1] [0] = 1
  for (let i = 1; i <= len; i++) {
    dp[0].push(dp[0][i - 1] * nums[i - 1])
    dp[1].push(dp[1][i - 1] * nums[len - i])
  }
  for (let i = 1; i <= len; i++) {
    res[i - 1] = dp[0][i - 1] * dp[1][len - i] 
  }
  return res
};
Copy the code

Here are a few caveats:

  1. No length is given when initializing the DP array

    Because I’m using push here, it doesn’t make sense to give a length here, it’s ok to give a length, but there’s no need to use push, it’s ok

  2. DP array initialization assignment

    The DP array is one digit longer than nums, Why? Because of the problem between the first element and the last element, if the value of the first element is calculated, then obviously dp[0][i-1] does not exist, and then there will be a problem with the dp formula. Put an extra 1 in front of dp[1] to prevent the problem of failing to get the value. As a reverse array, dp[1] naturally needs to do the same operation. Otherwise, there will be a problem of not getting a value

After successfully fetching the DP array, the last for loop will fetch the final RES, clear and clear

A better way (DP+ singular group)

Although the solution of 👆 is AC, it still does not meet the meaning of the question, because the space complexity is O(n), after all, there is the existence of DP array.

So how do we optimize to order one? Notice they say res doesn’t really count as O(n), because it’s a return value.

Then we have to do something about RES. Is that ok

  • toresWhen we initialize the assignment, we assign the value abovedp[0]An array of
  • And then use a variable to add updp[1]Array changes, in order toresTo assign a value

This saves the space for DP pairs, allowing the answer to conform to the spatial complexity of O(1).

var productExceptSelf = function(nums) {
  const len = nums.length
  const res = new Array(len)
  res[0] = 1
  for (let i = 1; i < len; i++) {
    res[i] = res[i - 1] * nums[i - 1]}let count = 1
  for (let i = len - 1; i >= 0; i--) {
    res[i] = res[i] * count
    count *= nums[i]    
  }
  return res
};
Copy the code

The overall solution is this: the first for loop is used to initialize the RES, then the count variable is accumulated and assigned to the elements in the RES, so that after two for loops, the RES gets the final result.





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)