A diary of dishes | 238 Product of arrays other than itself

Series index ： Writing diary of vegetables | By LeetCode use Python The days of abuse

The way of cultivating immortality of vegetable chicken ——2022/1/12

List of articles

• • 【 subject 】
  • 【 Official thinking 】
  • 【 Reference code 】
  • 【 reflection 】

【 subject 】

Give you a length of n Array of integers for nums, among n > 1, Return output array output , among output[i] be equal to nums Middle Division nums[i] Product of other elements .

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

Tips ： The title data guarantees all prefix elements and suffixes of any element in the array （ Even the entire array ） The product of is all in 32 Bit integer range .

explain : Please do not use division , And in O(n) Complete this question in time complexity .

Topic link ：https://leetcode-cn.com/problems/product-of-array-except-self/

【 Official thinking 】

Old rules , It depends on the official solution . I have to say that it's interesting to see the boss solve the problem 、

Method 1 ： Construct two lists to store the product of prefix and suffix respectively ,anwser It's the product of the two , Three times in total .

Advanced ： Advanced repeated borrowing anwser To save space and complexity , Use here R To temporarily store suffix product data , Get a new R Then take it directly to anwser In the . Play a “ One for one group ” The role of .

The code can be studied , From the video .

【 Reference code 】

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1 for i in range(len(nums))]

        left = 1
        for i in range(len(nums)):
            res[i] *= left
            left *= nums[i]

        right = 1
        for i in range(len(nums)-1, -1, -1):
            res[i] *= right
            right *= nums[i]
        return res

【 reflection 】

Have to say , I feel ashamed that I have been reading computer code for nearly three years , Although the Internet of things is biased towards engineering practice , But from the perspective of personal planning, we still need to improve our algorithm level , come on. , It's never too late to learn ！

Python The series of force buckle problem solving is continuously updated , welcome Like collection ＋ Focus on

Last one ： Writing diary of vegetables | 189. Rotation array rotate-array
Next ： Writing diary of vegetables | 118. Yang hui triangle

My level is limited , Please comment and correct the deficiencies in the article in the comment area below ~

If feelings help you , Point a praise Give me a hand ~

Share... From time to time Interesting 、 Have a material 、 Nutritious content , welcome Subscribe to follow My blog , Looking forward to meeting you here ~