有序数组的平方
题目描述
给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。-10^4 <= nums[i] <= 10^4
示例 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]
思路
题目要求
- 给定一个含负数的升序排列的数组，
- 返回每个数字的平方组成的新的升序数组
暴力解法：平方后排序
暴力解法没有利用题目中给到的条件：给定一个含正负数的升序数组。所以平方以后的大值肯定出现在两侧，不是左边就是右边（负数的平方为正数）。
双指针法：两个指针分别指向数组的首部和尾部，每次比较两个指针所指值的大小，将大的逆序放入新数组。将双指针从外向内移动不会发生数组越界问题。
注意
因为是逆序存入数组，所以for循坏的循坏变量i从len(nums)-1开始递减。
代码
Go
func sortedSquares(nums []int) []int {
length := len(nums)
left, right := 0, length-1
newNums := make([]int, length)
for i := len(nums) - 1; i >= 0; i-- {
if l, r := nums[left]*nums[left], nums[right]*nums[right]; l < r {
newNums[i] = r
right--
} else {
newNums[i] = l
left++
}
}
return newNums
}
Link
版权声明：本文为m0_56510407原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。