题目
Given an integer array nums
sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums
is sorted in non-decreasing order.
Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n)
solution using a different approach?
思路
最简单的方式就是先对数组的每个数相乘,然后再为数组排序了,两行搞定,不过这样恐怕不符合这道题的本意。。。
真正的解法是双指针,初始化于数组的最左边和最右边,然后比对两个指针上数值绝对值的大小,其中较大的数值即为整个数组最大的数值,将其乘积取出并保存,随后左(右)移指针。如此循环,取出乘积组成的新数组便是答案。
代码
python版本:
# 双指针(超时)
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
i=0
l=len(nums)
while i<l:
if nums[i]<0:
nums[i]=-nums[i]
j=i
while j+1<len(nums) and nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
j+=1
else:
nums[i]=nums[i]*nums[i]
i+=1
return nums
# map再排序
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
nums=list(map(lambda x: x*x,nums))
return sorted(nums)
# 真正的双指针
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res=[0 for _ in range(len(nums))]
l,r,now=0,len(nums)-1,len(nums)-1
while now>=0:
if abs(nums[l])>abs(nums[r]):
res[now]=nums[l]*nums[l]
now-=1
l+=1
else:
res[now]=nums[r]*nums[r]
now-=1
r-=1
return res