1 題目

給你一個按 非遞減順序 排序的整數數組 nums，返回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。

2 解析

（1）方法一：使用python內置的sort的快排
空間復雜度O(n)，時間復雜度O(nlogn)
（2）方法二
直接插入排序，但是超過時間限制
時間復雜度 O ( n 2 ) O(n^2) O(n2)，時間復雜度O(1)
（3）方法三
雙指針
時間復雜度O(n)，空間復雜度O(n)

3 python 實現

（1）方法一

# 快速排序
def sortedSquares(self, nums: List[int]) -> List[int]:
res = []
for i in nums:
res.append(i*i)
# 第一種方法，使用python內置的sort方法
res.sort()
# 第二種方法，自己寫快排算法
self.QuckSort(res,0,len(nums)-1)
return res
def partition(self,arr,low,high):
i = low-1
pivot =arr[high]
for j in range(low,high):
if arr[j]<=pivot:
i+=1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return i+1
def QuckSort(self,arr,low,high):
if low <high:
p = self.partition(arr,low,high)
self.QuckSort(arr,low,p-1)
self.QuckSort(arr,p+1,high)

（2）方法二

 # 直接插入排序;注意，超過時間限制
def sortedSquares(self, nums: List[int]) -> List[int]:
if len(nums)==0:
return nums
nums[0] = nums[0]*nums[0]
for i in range(1,len(nums)):
temp = nums[i]*nums[i]
j=i-1
while j>=0 and temp<nums[j]:
nums[j+1] =nums[j]
j -=1
nums[j+1] = temp
return nums

（3）方法三

# 雙指針
def sortedSquares(self, nums: List[int]) -> List[int]:
if len(nums)==1:
return [nums[0]*nums[0]]
res = [-1]*len(nums)
idx = len(nums)-1
right =len(nums)-1
left = 0
while left<=right:
if nums[left]*nums[left]>nums[right]*nums[right]:
res[idx] = nums[left]*nums[left]
left +=1
else:
res[idx] = nums[right]*nums[right]
right -=1
idx -=1
return res