leetcode--977. Squares of a Sorted Array

• Problem：Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. ¹

• Example ：

# Example 1
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
# Example 2
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

• Tips ：

1. 1 <= nums.length <= 104
2. -104 <= nums[i] <= 104
3. nums is sorted in non-decreasing order.

• Ideas ：

First, sort each value in the list
Output with built-in sorting algorithm

• Solution 1 – direct ：

class Solution:
    def sortedSquares(self, nums):
        dou_nums = [x * x for x in nums]
        return sorted(dou_nums)

• Ideas ：

Set an empty list to store qualified values , Set the head and tail pointer to head and tail
When the head pointer is not equal to the tail pointer , Continue operation , If the square of the head is greater than the square of the tail , Insert the header value into the list and add one to the pointer ; If the square of the tail value is greater than or equal to the square of the head value , Insert the square of the tail value into the list and add one to the tail pointer ; If the head pointer is greater than or equal to the tail pointer , And then jump out of the loop
Insert the remaining header values squared into the list
Returns the reverse order of the list

• Solution 2 – Double pointer ：

class Solution:
    def sortedSquares(self, nums):
        dou_nums = []
        a, b = 0, len(nums)-1
        while a != b:
            dou_a = nums[a] ** 2
            dou_b = nums[b] ** 2
            if dou_a > dou_b:
                dou_nums.append(dou_a)
                a += 1
            elif dou_b >= dou_a:
                dou_nums.append(dou_b)
                b -= 1
            if a >= b:
                break
        dou_nums.append(nums[a]**2)
        return dou_nums[::-1]