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

preface

Algorithm as an extremely important point, is the core competitiveness of college graduates looking for a job, so in order not to lag behind with people, began to brush force buckle algorithm!

The first time, do not seek the optimal solution, but beg can pass!!

📢 this is my brush 9/100 buckle simple question

1. Title Description

Given an array of integers sorted in non-descending order, nums returns a new array of the squares of each number, also sorted in non-descending order.

Tip:

1 <= nums.length <= 104-104 <= nums[I] <= 104 NUMs have been sorted in non-descending order

Advanced:

Please design an algorithm with O(n) time complexity to solve this problem

Second, the instance

The sample1: Enter nums = [-4, -1.0.3.10] output: [0.1.9.16.100] the array becomes [16.1.0.9.100After sorting, the array becomes [0.1.9.16.100] example2: Enter nums = [-7, -3.2.3.11] output: [4.9.9.49.121]
Copy the code

Third, the idea of solving the problem

  1. Use the built-in function method

    Traversal, square, compare, sort

    Sorting can be done using the built-in function SQRT ()

  2. Double pointer method

    Since the original array/list was ordered, but squared and then sorted, the two-pointer method can be used

    It’s kind of like binary search

    We need two numbers to record the left and right side of the array/list

    Then compare the left and right sizes and add the larger ones to an array/list

    This last array/list is our answer

Three, code,

  1. Built-in function method

    Time complexity: O(n)

    Space complexity: O(1)

    from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) - >List[int] :
        ans = []
        for i in nums:
            ans.append(i**2)
        return sorted(ans)
Copy the code

  2. Double pointer method

    Time complexity: O(n)

    Space complexity: O(1)

    class Solution:
    def sortedSquares(self, nums: List[int]) - >List[int] :
        ans = []
        n = len(nums)
        m = 0
        while m <= n-1:
            i = nums[m]*nums[m]
            j = nums[n-1]*nums[n-1]
            if i >= j:
                ans.append(i)
                m += 1
            else:
                ans.append(j)
                n -= 1
        return ans[::-1]
Copy the code

conclusion

Adhere to the most important, a daily indispensable!