问题描述:
给定一个按非递减顺序排序的整数数组 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 已按非递减顺序排序。
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
#左指针
left = 0
#右指针
right = len(A)-1
#用于存储结果
res = [0 for _ in range(len(A))]
#从右至左遍历数组
for i in range(len(A)-1,-1,-1):
#计算左指针指向值得平方
l = A[left]*A[left]
#计算右指针指向值得平方
r = A[right]*A[right]
#如果l<=r
if l <= r:
#将res的第i位更新为r
res[i] = r
#因为是非递键排序的,所以剩下的值都会比该值小了,此时右指针减一
right -= 1
else:
res[i] = l
left += 1
return res
结果: