LeetCode——977.有序数组的平方（C++）-创新互联

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

暴力解法这里就不讲解了，重点是双指针法。

我们从题目可以知道，数组是按升序排列的，可以有以下三种情况：

• 数组元素全都是非负数的情况下，平方之后的数据依然也是升序的；
• 数组元素全都是负数的情况下，平方之后的数据则是降序的；
• 数组元素有非负也有负数，平方之后的数据先减小后增大

这样看来，我们可以先找到数组中负数和非负数的分界线，记为flag，分界线左边为负数，非负数的右边为非负数

由图可知：

• nums[0] ~ nums[flag] 全是负数
• nums[flag+1] ~ nums[nums.size()-1] 全是非负数

当将原数组的数据平方之后，nums[0] ~ nums[flag]是单调递减的， nums[flag+1] ~ nums[nums.size()-1]是单调递增的

具体实现：

• 定义一个结果数组ans
• 定义两个指针 i 和 j 分别指向 flag 和 flag+1 的位置，即 i = flag，j = flag+1；
• 每次比较nums[i]和nums[j]的大小，选择小的数据添加到ans中
• 如果 i< 0 或者 j = nums.size()，则表示某一方移到了边界，则将另一方还未遍历的数据依次添加到ans中

class Solution {
public:
    vectorsortedSquares(vector& nums) {
        int n = nums.size();
        int flag= -1;
        //找到最后一个负数的位置
        for (int i = 0; i < n; ++i){
            if (nums[i] < 0){
                flag= i;
            } else {
                break;
            }
        }
        //结果数组
        vectorans;
        //i为最后一个数组的位置，j为第一个>=0的位置
        int i = flag, j = flag+ 1;
        while (i >= 0 || j < n){
            //此时小于0的数已经全部放进结果集，只需看j的
            if (i < 0){
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
            //此时j那边的数已经全部遍历完
            else if (j == n){
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            //i的平方小于j的平方
            else if(nums[i] * nums[i] < nums[j] * nums[j]){
                ans.push_back(nums[i] * nums[i]);
                --i;
            }
            //i的平方大于j的平方
            else{
                ans.push_back(nums[j] * nums[j]);
                ++j;
            }
        }
        return ans;
    }
};
 

复杂度分析：

时间复杂度：O(n)，其中 nn是数组nums 的长度。

空间复杂度：O(1)，除了存储答案的数组以外，我们只需要维护常量空间。

数组其实是有序的， 只不过负数平方之后有可能会成为大数，从而变成了先递减后递增的数组。那么数组平方的大值就在数组的两端，不是在最左边就是最右边，而不可能在中间。此时我们依然可以考虑双指针法。

• 定义 i 指向数组起始位置，定义 j 指向数组终止位置
• 定义一个新数组ans，和nums数组一样的大小，让 k 指向 ans 数组的终止位置。
• 如果nums[i] * nums[i]< nums[j] * nums[j] 那么ans[k--] = nums[j] * nums[j];
• 如果nums[i] * nums[i] >= nums[j] * nums[j] 那么ans[k--] = nums[i] * nums[i]; 

class Solution {
public:
    vectorsortedSquares(vector& nums) {
        int n = nums.size();
        vectorans(n);
        int i = 0;//数组的起始位置
        int j = n - 1;//数组的终止位置
        int k = n - 1;//ans数组插入数据的位置
        while(i<=j)
        {
            if(nums[i]*nums[i] >nums[j]*nums[j])
            {
                ans[k] = nums[i]*nums[i];
                i++;
            }
            else
            {
                ans[k] = nums[j]*nums[j];
                j--;
            }
            --k;
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：O(n)，其中 nn 是数组 nums 的长度。

空间复杂度：O(1)，除了存储答案的数组以外，我们只需要维护常量空间。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧