双指针

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 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为O(n)的算法解决本问题

这道题如果要达到复杂度为\(O(n)\)的复杂度，方法可以为双指针法，理论上，我们只需要遍历数组一次，就可以将其排序结束并输出。

题目分析

对于示例一：

我们找到两个指针，一个为left，一个为right。其中right为nums[right]>=0，即正负分界点，left为right的前一个点。当然，如果整个数组全为正数，right==left==0

接下来的步骤为比较

if(nums[left]*nums[left]>nums[right]*nums[right]){
    ans.push_back(nums[right]*nums[right]);
    right++;
}
else{
    ans.push_back(nums[left]*nums[left]);
    left--;
}    

我们比较nums[left]*nums[left]和nums[right]*nums[right]的大小，将小的放入数组，然后进行指针的移动，left左移或者右移。直至left==-1或者right==size的时候，我们将剩下的元素入列。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //先排序后平方
        //双指针法
        int size = nums.size();
        int left;
        int right;
        //找到正负的交界点
        right = 0;
        while(right>=0&&right<size){
            if(nums[right]>=0)
                break;
            else
                right++;
        }
        if(right>0)
            left = right-1;
        else
            left = right;
        vector<int> ans;
        if(right==0){
            for(int i=0;i<size;i++){
                ans.push_back(nums[i]*nums[i]);
            }
        }
        else{
            while(left>=0&&right<size){
                if(nums[left]*nums[left]>nums[right]*nums[right]){
                ans.push_back(nums[right]*nums[right]);
                right++;
                }
                else{
                    ans.push_back(nums[left]*nums[left]);
                    left--;
                }    
            }
            //插入剩下的元素
            if(right==size){
                while(left>=0){
                    ans.push_back(nums[left]*nums[left]);
                    left--;
                }
            }
            else if(left==-1){
                while(right<size){
                    ans.push_back(nums[right]*nums[right]);
                    right++;
                }
            }
        }
        return ans;
    }
};