手机软件下载网站推荐如何设置友情链接

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

方法一：直接将每个元素的平方压入ans数组中，再对ans数组进行排序

class Solution 
{
public:vector<int> sortedSquares(vector<int>& nums) {vector<int>ans;for(int x:nums){ans.emplace_back(x*x);}sort(ans.begin(),ans.end());return ans;}
};

方法二：双指针

题目给我们的数组是一个非递减的数组，那么我们可以利用好这个条件减小时间复杂度。

操作方法如下：由于是非递减数组，并且其中可能有负数，那么平方后最大的两个数只有可能是第一个（即负数中最小的那个）和最后一个（即正数中最大的那个）。我们可以想到双指针，一个从前往后，一个从后往前，分别比较指向元素平方后的大小。然后给一个位置指针k，标记要存入的位置。比较后我们将较大的元素存到k这个位置，然后k自减，指向平方后较大的元素的指针就移动一位，重复上述过程

class Solution 
{
public:vector<int> sortedSquares(vector<int>& nums) {vector<int>ans(nums.size(),0);int k=nums.size()-1;int i=0,j=k;while(i<=j)//要取等，否则若有奇数个元素，中间那个会没有处理{if(nums[i]*nums[i]<nums[j]*nums[j]){ans[k--]=nums[j]*nums[j];j--;}else{ans[k--]=nums[i]*nums[i];i++;}}return ans;}
};