有序数组的平方
LeetCode977. 有序数组的平方
题目描述
给你一个按非递减顺序排序的整数数组 nums
,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。 -10^4 <= nums[i] <= 10^4
示例 1:
1
2
3
4
|
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
|
示例 2:
1
2
|
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
|
思路
题目要求
- 给定一个含负数的升序排列的数组,
- 返回每个数字的平方组成的新的升序数组
暴力解法:平方后排序
暴力解法没有利用题目中给到的条件:给定一个含正负数的升序数组。所以平方以后的大值肯定出现在两侧,不是左边就是右边(负数的平方为正数)。
双指针法:两个指针分别指向数组的首部和尾部,每次比较两个指针所指值的大小,将大的逆序放入新数组。将双指针从外向内移动不会发生数组越界问题。
注意
因为是逆序存入数组,所以for
循坏的循坏变量i
从len(nums)-1
开始递减。
代码
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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
GitHub