977. 有序数组的平方

977. 有序数组的平方977. 有序数组的平方977. 有序数组的平方

给你一个按非递减顺序排序的整数数组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]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums已按非递减顺序排序

暴力做法：时间复杂度为nlogn

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int left=0; for(;left<nums.size();left++){ nums[left]=nums[left]*nums[left]; } sort(nums.begin(),nums.end()); return nums; } };

双指针做法：时间复杂度为n

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { vector<int> result(nums.size()); int k=nums.size()-1; for(int i=0,j=nums.size()-1;i<=j;){ if(nums[i]*nums[i]<nums[j]*nums[j]){ result[k]=nums[j]*nums[j]; j--; k--; } else { result[k]=nums[i]*nums[i]; i++; k--; } } return result; } };

因为最值只会出现在俩端，所以只需要左右两端的值进行比较即可，把大的数放在数组的最右端，再移动某一个含大值端的指针。

注意：左右俩端指针相同情况也得考虑，不然就忽视了那个元素了