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]

• 提示：

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

• 思路：

首先将列表中的每个值排序
采用内置排序算法输出

• 解法一–直接：

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

• 思路：

设置一个空列表存储符合条件的值，设置头尾指针指向头尾
当头指针不等于尾指针时，继续运行，若头值平方大于尾的平方，则将头值插入列表并指针加一；若尾值平方大于等于头值平方，则将尾值平方插入列表并尾指针加一；若头指针大于等于尾指针，则跳出循环
将剩下的头值平方插入列表
返回列表的倒序

• 解法二–双指针：

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]