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