有序数组的平方数

题目表述

给你一个按 非递减顺序 排序的整数数组 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]

提示

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

进阶：请你设计时间复杂度为 O(n) 的算法解决本问题

解法一：数组双向遍历

从中间的分界点开始，双向遍历数组，每次将平方较小者加入结果数组（Python实现）。

也可以从两边开始，从大往小添加（Go实现）

时间复杂度：O(n) 空间复杂度：O(n)

代码实现

from typing import List


class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 储存结果数组
        ans = [0] * len(nums)
        # 查找正负数的分界点
        if nums[0] >= 0:
            zero_idx = 0
        elif nums[-1] <= 0:
            zero_idx = len(nums) - 1
        else:
            for i in range(1, len(nums)):
                if nums[i-1] * nums[i] <= 0:
                    zero_idx = i-1
                    break
        # 从零点开始双向遍历
        i, j = zero_idx, zero_idx + 1
        pidx = 0
        while i>=0 and j < len(nums):
            lval = nums[i]**2
            rval = nums[j]**2
            if lval <= rval:
                ans[pidx] = lval
                i -= 1
            else:
                ans[pidx] = rval
                j += 1
            pidx += 1
        # 单边剩余部分
        while i >= 0:
            ans[pidx] = nums[i]**2
            i -= 1
            pidx += 1
        while j < len(nums):
            ans[pidx] = nums[j]**2
            j += 1
            pidx += 1
        return ans


if __name__ == "__main__":
    nums = [-1, 2, 2]
    res = Solution().sortedSquares(nums)
    print(res)

package leetcode

func sortedSquares(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	left, right, pidx := 0, n-1, n-1
	for left < right {
		lval := nums[left] * nums[left]
		rval := nums[right] * nums[right]
		if lval >= rval {
			ans[pidx] = lval
			left += 1
		} else {
			ans[pidx] = rval
			right -= 1
		}
		pidx -= 1
	}
	return ans
}