给定一个按非递减顺序排序的整数数组 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 已按非递减顺序排序。
一开始也是没有什么思路,连排序都没想到,后来参考了一下专家的解法,豁然开朗
方法一:排序
思路与算法
创建一个新的数组,它每个元素是给定数组对应位置元素的平方,然后排序这个数组。这对于Python比较方便,它有自带的sort方法
方法二:双指针
思路
因为数组 A 已经排好序了, 所以可以说数组中的负数已经按照平方值降序排好了,数组中的非负数已经按照平方值升序排好了。
算法
首先,确定正值和负值临界点,然后正值部分向尾部走,负值部分向头部走。接下来就是比较数字平方的大小,依次放入一个空列表
class Solution:
def sortedSquares(self, A: List[int]) -> List[int]:
N = len(A)
j = 0
# determin negative and positive part
while (j < N) and (A[j] < 0):
j+=1
i = j-1
ans = []
while (i>=0 and j < N):
if(A[i]**2 < A[j]**2):
ans.append(A[i]**2)
i -= 1
else:
ans.append(A[j]**2)
j += 1
while i >= 0:
ans.append(A[i]**2)
i -= 1
while j<N:
ans.append(A[j]**2)
j += 1
return ans