【力扣】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]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

题解：

暴力排序：

// 时间复杂度：O(n log n)
// 空间复杂度：O(1)
func sortedSquares(nums []int) []int {
        // 求每个下标的平方
	for i, num := range nums {
		nums[i] = num * num
	}
        // 对数组进行快速排序一遍
	sort.Ints(nums)
	return nums
}

双指针法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func sortedSquares(nums []int) []int {
	n := len(nums)
	// l: left 代表数组的最左侧下标
	// r: right 代表数组最右侧的下标
	// k: 代表新数组的下标
	l, r, j := 0, n-1, n-1
	// 创建一个新的数组，长度和原数组相等
	ans := make([]int, n)
	for l <= r {
		// 将所有两边的数求平方
		left, right := nums[l]*nums[l], nums[r]*nums[r]
		// 比较两边的值的大小
		if left > right {
			// 左边的值大，则将左边的值存进新的切片
			ans[j] = left
			// 将左边的指针向右移动一位
			l++
		} else {
			// 右边的值大（或相等），则将右边的值存入新的切片
			ans[j] = right
			// 将右边的指针向左移动一位
			r--
		}
		// 每次循环更新新数组的下标
		j--
	}
	return ans
}