【题目】
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
进阶:
请你设计时间复杂度为 O(n) 的算法解决本问题
【代码】
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
right,left=len(nums),0
for idx,item in enumerate(nums):
if item>=0:
right=idx
break
rr=right
left=right-1
ans=[]
while rr<len(nums) and left>=0:
if nums[rr]<=abs(nums[left]):
ans.append(nums[rr]**2)
rr+=1
else:
ans.append(nums[left]**2)
left-=1
while rr<len(nums):
ans.append(nums[rr]**2)
rr+=1
while left>=0:
ans.append(nums[left]**2)
left-=1
return ans
【方法2】
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left,right=0,len(nums)-1
ans=[]
while left<=right:
l=nums[left]**2
r=nums[right]**2
if l>=r:
ans.insert(0,l)
left+=1
else:
ans.insert(0,r)
right-=1
return ans
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left,right=0,len(nums)-1
ans=[0 for i in range(len(nums))]
pos=len(nums)-1
while left<=right:
l=nums[left]**2
r=nums[right]**2
if l>=r:
ans[pos]=l
left+=1
else:
ans[pos]=r
right-=1
pos-=1
return ans