西安的网站设计单位,网站商城例子下载,dux大前端WordPress,石泉政协网站建设方案给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
方法一#xff1a;直接将每个元素的平方压入ans数组中#xff0c;再对ans数组进行排序
class Solution
{
public:vectorint sort…给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
方法一直接将每个元素的平方压入ans数组中再对ans数组进行排序
class Solution
{
public:vectorint sortedSquares(vectorint nums) {vectorintans;for(int x:nums){ans.emplace_back(x*x);}sort(ans.begin(),ans.end());return ans;}
};
方法二双指针
题目给我们的数组是一个非递减的数组那么我们可以利用好这个条件减小时间复杂度。
操作方法如下由于是非递减数组并且其中可能有负数那么平方后最大的两个数只有可能是第一个即负数中最小的那个和最后一个即正数中最大的那个。我们可以想到双指针一个从前往后一个从后往前分别比较指向元素平方后的大小。然后给一个位置指针k标记要存入的位置。比较后我们将较大的元素存到k这个位置然后k自减指向平方后较大的元素的指针就移动一位重复上述过程
class Solution
{
public:vectorint sortedSquares(vectorint nums) {vectorintans(nums.size(),0);int knums.size()-1;int i0,jk;while(ij)//要取等否则若有奇数个元素中间那个会没有处理{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;}
};
