題目

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. 1 <= A.length <= 10000
2. -10000 <= A[i] <= 10000
3. A is sorted in non-decreasing order.

題目大意

給一個已經有序的數組，返回的數組也必須是有序的，且數組中的每個元素是由原數組中每個數字的平方得到的。

解題思路

這一題由於原數組是有序的，所以要儘量利用這一特點來減少時間複雜度。

最終返回的數組，最後一位，是最大值，這個值應該是由原數組最大值，或者最小值得來的，所以可以從數組的最後一位開始排列最終數組。用 2 個指針分別指向原數組的首尾，分別計算平方值，然後比較兩者大小，大的放在最終數組的後面。然後大的一個指針移動。直至兩個指針相撞，最終數組就排列完成了。

��

參考代碼

package leetcode

import "sort"

// 解法一
func sortedSquares(A []int) []int {
	ans := make([]int, len(A))
	for i, k, j := 0, len(A)-1, len(ans)-1; i <= j; k-- {
		if A[i]*A[i] > A[j]*A[j] {
			ans[k] = A[i] * A[i]
			i++
		} else {
			ans[k] = A[j] * A[j]
			j--
		}
	}
	return ans
}

// 解法二
func sortedSquares1(A []int) []int {
	for i, value := range A {
		A[i] = value * value
	}
	sort.Ints(A)
	return A
}