This is the 27th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

The sum of the nearest three numbers, wonderful

LeetCode: Valid parentheses

Delete duplicates in LeetCode: delete duplicates in LeetCode

The container that holds the most water is the container that holds the most water

LeetCode 11 string multiplication: LeetCode string multiplication, what do you do?

LeetCode reverses the string. I’m cheating again!

LeetCode013: Reverses the word III in the string

Question 14: The product of arrays other than themselves. For the interview, I am looking forward to your joining us. “Use the utility in the API is recommended in the project. But if you Use it in an interview, You will definitely fail.”

Today’s topic

Given an integer array nums of length n, where n > 1, return 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

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.)

Three, the analysis

If you want to multiply an element and multiply the product of the other elements, you can multiply the product by two elements. O(n), hard, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hair, pull your hairoutputThe last element is the original listThe product of the first three numbersThe penultimate element is the original listThe product of the first two numbersandThe product of the last digitThe third to last element is the original listThe product of the previous numberandThe product of the last twoThe first element is the original listThe product of the last three, the specific ideas are as follows:

Fourth, the problem solving

1. Quick way:

Time complexity: O(n)

In terms of spatial complexity, regardless of the output list, the spatial complexity of the following code is: O(1)

(1) code

class Solution(object) :
    def productExceptSelf(self, nums) :
        """ :type nums: List[int] :rtype: List[int] """
        p = 1    # Raw data subscript
        n = len(nums)  The original list length
        output = []  # return list
        for i in range(0,n):
	    The first for loop implements the product of the first n digits
	    And store the result in the Output list
            output.append(p)
            p = p * nums[i]
        p = 1  Return to original data subscript
        for i in range(n-1, -1, -1) :The second for loop iterates backwards
	    And store the result in the Output list
            output[i] = output[i] * p
            p = p * nums[i] Take the product of the last n minus I bit
        return output
Copy the code

(2) Submit the results

Test data: 17 groups running time: 124ms beat percentage :59.68%

The ideas are clever and difficult to understand.

2. Here’s a better way to blow things up

Two lines of code. Here we call reduce, and it looks like O(n). We only see a for loop, but the reduce function is also traversal, so the time complexity is O(n^2).

(1) code

class Solution1:
    def productExceptSelf(self, nums) :
        """ :type nums: List[int] :rtype: List[int] """
        from functools import reduce
        return [ reduce(lambda x,y:x*y,nums[:i]+nums[i+1:)for i in range(len(nums))]
Copy the code

(2) Introduction of ideas(3) Submit results(4) Reduce function of minor knowledge

The reduce() function accumulates the elements in the argument sequence.

Function performs the following operations on all the data in a data set (linked list, tuple, etc.) : operates on the first and second elements of the set with function (which has two parameters) passed to Reduce, and then calculates the result with the third data using function function, finally obtaining a result.

reduce(function, iterable[, initializer])

Iterable: initializer: initializer: iterable: initializer: initializerCopy the code

To put it simply, reduce can iterate over the incoming iterable and perform specific operations on function, which is concise and demonstrates Python’s elegance.

Lambda functions

Lambda expressions, usually to a function, but don’t want to bother to name a function of situations, is refers to the anonymous functions, suitable for function relatively simple function, if the function function is complex, write a function that can be directly, or forced to lambda expressions is not easy to understand, but lost the readability of the program.

Although beat people are not many, but I have ideas, I am proud ~

Feel very cool, feel very hard, the reality is very cruel, have this feeling?

Five, doubt

The idea is very complicated,

The implementation is interesting,

As long as you don’t give up,

Fame will come. — “Old Watch doggerel”

Six, the concluding

Persistence and hard work: results.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di