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

问题描述:

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

成都创新互联公司专注于企业成都营销网站建设、网站重做改版、福田网站定制设计、自适应品牌网站建设、H5响应式网站商城建设、集团公司官网建设、成都外贸网站建设公司、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为福田等各大城市提供网站开发制作服务。

算法分析:

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

方法一 :双指针(一)

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

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

这样看来,我们可以先找到数组中负数和非负数的分界线,记为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元起,快前往官网查看详情吧


标题名称:LeetCode——977.有序数组的平方(C++)-创新互联
链接分享:http://scyanting.com/article/docopg.html