题目
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
解题
方法一：直接排序
python解法
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: return sorted([num**2 for num in nums])
c++解法
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> res; for(int num:nums){ res.push_back(num*num); } sort(res.begin(),res.end()); return res; } };
java解法
class Solution { public int[] sortedSquares(int[] nums) { int[] res=new int[nums.length]; for(int i=0;i<nums.length;i++){ res[i]=nums[i]*nums[i]; } Arrays.sort(res); return res; } }
这个时间复杂度是 O(n + nlogn)， 可以说是O(nlogn)的时间复杂度
方法二：双指针
数组平方的最大值就在数组的两端，不是最左边就是最右边,，不可能是中间。
python解法
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) i,j,k = 0,n-1,n-1 res = [-1]*n while i<=j: lm = nums[i]**2 rm = nums[j]**2 if lm>rm: res[k]=lm i+=1 else: res[k]=rm j-=1 k-=1 return res
c++解法
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); int i=0,j=n-1,k=n-1; vector<int> res(n); while(i<=j){ int lm=nums[i]*nums[i]; int rm=nums[j]*nums[j]; if(lm>rm){ res[k]=lm; i++; } else{ res[k]=rm; j--; } k--; } return res; } };
java解法
class Solution { public int[] sortedSquares(int[] nums) { int[] res=new int[nums.length]; int i=0,j=nums.length-1; int k=nums.length-1; while(i<=j){ int lm=nums[i]*nums[i]; int rm=nums[j]*nums[j]; if(lm>=rm){ res[k]=lm; i++; }else{ res[k]=rm; j--; } k--; } return res; } }
此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlogn)还是提升不少的。
