977. 有序数组的平方

[yankewei]

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

示例 1：

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

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= A.length <= 10000
• -10000 <= A[i] <= 10000
• A 已按非递减顺序排序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array

[yankewei]

排序

最简单的就是先计算，之后排序即可

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

数组

既然数组的值已经限制，那我可以创建一个包含10000个元素的数组slice，然后，遍历A，每个元素落到slice的位置上。

func sortedSquares(A []int) []int {
    var slice [10001]int
    var ret []int
    for _, v := range A {
        if v < 0 {
            slice[-v]++
        } else {
            slice[v]++
        }
    }
    for i, v := range slice {
        if v > 0 {
            for ii := 0; ii < v; ii++ {
                ret = append(ret, i*i)
            }
        }
    }
    return ret
}

双指针

声明一个数组ans，然后左右两个指针，指向开头和结尾，

1. 左边的平方大于右边的平方，放入ans的末尾，左指针++
2. 右边的平方大于左边的平方，放入ans的末尾，右指针--

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