[LeetCode]238. Solution to the product of arrays other than itself

Question

Give you an integer array nums of length n, where n > 1, return the output array output, where output[i] is equal to all other elements in nums except nums[i] product of.

Example:

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

Tips: The question data ensures that the product of all prefix elements and suffixes (even the entire array) of any element in the array is within the range of 32-bit integers.

Instructions: Pleasedo not use division, and complete this question within O(n) time complexity.

Advanced: Can you complete this problem within constant space complexity? (For the purpose of space complexity analysis, the output array is not considered extra space.).

Solution

The first idea when I get the question is: two for loops, one for product and one for division. But later I found that the instructions stated not to use division, so I had to use other methods.

Since we are calculating the cumulative multiplication other than ourselves, we can use the current position as the dividing point to calculate the product of the elements on the left and the product of the elements on the right respectively, and then multiply them.

The following solution is used for this:

Algorithm 1 (extracted from LeetCode official solution):

Initialize two empty arrays L and R. For a given index i, L[i] represents the product of all the numbers to the left of i, and R[i] represents the product of all the numbers to the right of i.

We need to use two loops to fill the values ​​of the L and R arrays. For the array L, L[0] should be 1 because there is no element to the left of the first element. For other elements: L[i] = L[i-1] * nums[i-1].

Similarly, for the array R, R[length-1] should be 1. length refers to the size of the input array. Other elements: R[i] = R[i 1] * nums[i 1].

When the R and L arrays are filled, we only need to iterate over the input array, and the value at index i is: L[i] * R[i].

class Solution {
    public int[] productExceptSelf(int[] nums) {
  int arrLen = nums.length;
  int[] leftNums = new int[arrLen];
  int[] rightNums = new int[arrLen];
  leftNums[0] = 1;rightNums[arrLen-1] = 1;
  
  for(int i = 1; i < arrLen; i++){
   leftNums[i] = leftNums[i-1] * nums[i-1];
   rightNums[arrLen-i-1] = rightNums[arrLen-i] * nums[arrLen-i];
  }
  
  for(int i = 0; i < arrLen; i++){
   leftNums[i] *= rightNums[i];
  }
  
  return leftNums;
 }
}

Complexity analysis

Time complexity:O(N), where N refers to the size of the array nums. Preprocessing the L and R arrays and the final traversal calculation are both O(N) time complexities.

Space complexity: O(N), where N refers to the size of the array nums. The L and R arrays are used to construct the answer. The length of the L and R arrays is the size of the array nums.

Algorithm 2: Shared array method

The overall idea is the same as the official problem-solving idea: Left multiplication*Right multiplication.

Define the return arrayreturnNums And treat it as a shared array, filling data from the left and right ends at the same time; then define left and right to store the left and right products and loop iteration renew.

1. Before the two pointers meet, you only need to simply fill the array;

2. When the two interact (only occurs in odd length) its padding value is left*right.

3. After the two are intersected, the value of the array should be filled in with the final value: because the left part has already stored the left product, and the right product is about to be calculated; the right part has stored the right product, we are about to get the left product. So just multiply them directly. returnNums[i] = left and returnNums[j] = right.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int arrLen = nums.length;
        int[] returnNums = new int[arrLen];
        int left = 1, right = 1;    // 临时存储
        returnNums[0] = 1; returnNums[arrLen-1] = 1;
        for(int i = 1, j = arrLen-2; i < arrLen; i++, j--){
            left *= nums[i-1];
            right *= nums[j+1];
            if(i < j){  // 两指针为交会
                returnNums[i] = left;
                returnNums[j] = right;
            }else if(i == j){   // 两指针重合，奇数位情况下发生
                returnNums[i] = left*right;
            }else{              // 两指针错位
                returnNums[i] *= left;
                returnNums[j] *= right;
            }
        }
        return returnNums;
    }
}

Complexity analysis

##Time complexity: O(N ), in the same way as the previous problem, a loop of length N is performed, and its time complexity is O(N).

Space complexity: O(1), as mentioned in the title, the space of the returned array is not counted, so the additional storage space used is left and right . Therefore, there is only constant level space complexity.

The above is the detailed content of [LeetCode]238. Solution to the product of arrays other than itself. For more information, please follow other related articles on the PHP Chinese website!