977. 有序数组的平方

一、 问题描述

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

示例

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

二 、方案一：直接排序

1、思路

• 遍历数组，计算每个元素的平方。
• 使用排序算法（如快速排序、归并排序等）对结果进行排序。

2、代码实现

func sortedSquares(A []int) []int {
    for i, v := range A {
        A[i] = v * v
    }
    sort.Ints(A)
    return A
}

3、复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是数组 A 的长度。排序的时间复杂度为 $O(n \log n)$。
• 空间复杂度：$O(\log n)$，排序可能需要 $O(\log n)$ 的栈空间。

三、 方案二：双指针

1、思路

• 由于数组 A 是非递减排序的，我们可以使用双指针方法。
• 一个指针指向第一个元素，另一个指针指向最后一个元素。
• 比较两个指针所指元素的平方，将较大的平方添加到结果数组的末尾，并移动相应指针。

2、代码实现

func sortedSquares(A []int) []int {
    n := len(A)
    ans := make([]int, n)
    i, j := 0, n-1
    for k := n - 1; k >= 0; k-- {
        if v, w := A[i]*A[i], A[j]*A[j]; v > w {
            ans[k] = v
            i++
        } else {
            ans[k] = w
            j--
        }
    }
    return ans
}

3、复杂度分析

• 时间复杂度：$O(n)$，只遍历数组 A 一次。
• 空间复杂度：$O(n)$，需要额外空间存储结果数组。

四、总结

• 方案一适合于数组较大，对空间要求不高的情况。
• 方案二在时间和空间上都更优，特别是对于较大的数组。