977. 有序数组的平方

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1:

输入：nums = [-4,-1,0,3,10]

输出：[0,1,9,16,100]

解释：平方后，数组变为 [16,1,0,9,100]. 排序后，数组变为 [0,1,9,16,100]

示例 2:

输入：nums = [-7,-3,2,3,11]

输出：[4,9,9,49,121]

题解

双指针

Go

func sortedSquares(nums []int) []int {
    n := len(nums)
    i, j, k := 0, n - 1, n - 1
    ans := make([]int, n)
    for i <= j {
        lm, rm := nums[i]*nums[i], nums[j]*nums[j]
        if lm > rm {
            ans[k] = lm
            i++
        } else {
            ans[k] = rm
            j--
        }
        k--
    }
    return ans
}

Python

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, i = 0, len(nums) - 1, len(nums) - 1
        res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果
        while l <= r:
            if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值
                res[i] = nums[r] ** 2
                r -= 1 # 右指针往左移动
            else:
                res[i] = nums[l] ** 2
                l += 1 # 左指针往右移动
            i -= 1 # 存放结果的指针需要往前平移一位
        return res

复杂度

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(1)\)