1. Title Description

The finger of the sword Offer 66. Building a product array

Given an array A[0,1,…,n-1], Please build an array B[0,1,…,n-1], among  B[i] Is the value of an array A In addition to subscript i The product of other elements , namely  B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]. Division cannot be used .

Example :

 Input : [1,2,3,4,5]
 Output : [120,60,40,30,24]

2. Problem solving ideas and codes

2.1 Their thinking

The question requires to get the product of the number of the array except the current bit , The first thought is to find the product of all numbers in the array , Then divide by the current bit , But if such a method encounters 0 It's going to be a mistake . Here you can use the idea of prefixes and arrays , First, traverse from left to right to get the product of the number on the left of the current bit , Then traverse from right to left to get the product of all bits on the right of the current number , Finally, multiply the product of the left and right sides of the current number to get the final result . With [1, 2, 3, 4, 5] As an example
First, we prepare an array to store the product of all numbers on the left of the number . Let the first be 1, Then it's convenient from left to right , Get the product to the left of the current number in turn

Then prepare an array to store the product of all the numbers on the right of the number . Set the last bit of the array to 1, Then traverse from right to left , Get the product of all numbers on the right of the current number in turn

Finally, multiply the two arrays by phase in order to get the final result

2.2 Code

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

    }
}

2.3 test result

Pass the test

3. summary

• Use the prefix and array idea to obtain the product of all numbers on the left and the product of all numbers on the right
• Multiply the left and right products in turn to get the final result