977. Squares of a Sorted Array

描述

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

解法

列表解析加 sorted 函数

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted([x * x for x in A])

类似的还可以用 map

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted(list(map(lambda x: x * x, A)))

复杂度分析：

• 时间复杂度: $O(N \log N), N 是数组 A 的长度。$

• 空间复杂度: $O(N)$

双指针

可以发现如果同时存在正负数的情况下，最大值将在两边端点产生，因此从两端向中间遍历，每次将最大值存入结果列表中，再移动对应指针，直到两根指针重合（l == r），等于的情况要考虑是因为该值也需要计算并存入结果数组中。

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        res = [0] * len(A)  # use a collections.deque() is also fine.
        l, r = 0, len(A) - 1

        while l <= r:
            left, right = abs(A[l]), abs(A[r])
            if left > right:
                res[r - l] = left * left
                l += 1
            else:
                res[r - l] = right * right
                r -= 1

        return res

时间复杂度和空间复杂度都是 $O(n)$。