给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
当0号位小于0时,取出,使用二分查找将其绝对值插入,最后一起平方。注意长度为1时单独讨论
不忍直视
class Solution(object): def sortedSquares(self, nums): """ :type nums: List[int] :rtype: List[int] """ lenn = len(nums) if(lenn==1): nums[0] *= nums[0] return nums while(nums[0]<0): temp = abs(nums[0]) #取出第一个负数的绝对值 del nums[0] #删除第一个负数 start,end = 0,lenn-2 mid = (start + end) / 2 while(start <= end): mid = (start+end)/2 if(temp == nums[mid]): nums.insert(mid+1,temp) break #插入,跳出 elif(temp > nums[mid]): start = mid+1 else: end = mid-1 if(start > end):#没找到相等的 if(temp>nums[mid]): nums.insert(mid + 1, temp) else: nums.insert(mid, temp) for i in range(0,lenn): nums[i] *= nums[i] return nums
头尾一起
class Solution(object): def sortedSquares(self, nums): """ :type nums: List[int] :rtype: List[int] """ '''双指针''' reslst = [] front,post = 0,len(nums)-1 while(front != post): f = abs(nums[front]) p = abs(nums[post]) if(f>p): reslst.insert(0,f*f) front+=1 else: reslst.insert(0,p*p) post-=1 reslst.insert(0, nums[front]*nums[front]) return reslst
但是这样时间很长,可能因为每次都在第一个加,动态变化 ,可以直接把答案列表设置成n个长度,用pos记录存放位置
class Solution: def sortedSquares(self, nums): n = len(nums) ans = [0] * n i, j, pos = 0, n - 1, n - 1 while i <= j: if nums[i] * nums[i] > nums[j] * nums[j]: ans[pos] = nums[i] * nums[i] i += 1 else: ans[pos] = nums[j] * nums[j] j -= 1 pos -= 1 return ans