首页 > 其他分享 >977.有序数组的平方

977.有序数组的平方

时间:2022-11-30 18:47:53浏览次数:62  
标签:977 平方 nums int res vector 数组 size

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

 

code:

  我的思路是先找到一个左邻是负数,右邻是非负数的两个位置,然后比较这两个位置,把小的插入到新数组的末尾,直到将所有的数都插入。

  但是实现的时候,发现并不容易实现,相较于双指针从首尾往中间汇合,首先要考虑只有一个元素的情况,此时并不存在右邻,所以溢出,其次要考虑全为负数的时候,此时右邻也是溢出的。所以总共分为三种情况。

#include<vector>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i, j;
        vector<int> res;
        if (nums.size() == 1)//此时只有一个元素
        {
            nums[0] = nums[0] * nums[0];
            res.insert(res.end(), nums[0]);
            return res;
        }
        for(i = 0; i < nums.size()-1; i++)
        {
            j = i + 1;
            if (nums[i] < 0 && nums[j] >= 0)
            {
                break;
            }
        }
        if (nums[j] < 0)//此时全为负数
        {
            for (j; j >= 0; j--)
            {
                nums[j] = nums[j] * nums[j];
                res.insert(res.end(), nums[j]);
            }
            return res;
        }
        if (i >= 0 && nums[0] < 0)
        {
            int b = i + 1;
            for (int a = i; a >= 0; a--)
            {
                nums[a] = nums[a] * (-1);
                while(b<= nums.size() - 1 && nums[b] <= nums[a])
                {
                    res.insert(res.end(), nums[b++]);
                }
                res.insert(res.end(), nums[a]);
            }
            while (b < nums.size())
            {
                res.insert(res.end(), nums[b++]);
            }
            for (auto& c : res)
            {
                c = c * c;
            }
            return res;
        }
        else {
            for (auto& c : nums)
            {
                c = c * c;
                res.insert(res.end(), c);
            }
            return res;
        }
        
            
    }
};
int main() {
    vector<int> nums = { 0,2 };
    vector<int> res;
    Solution a;
    res = a.sortedSquares(nums);
    for (const auto c : res)
    {
        cout<< c<<" ";
    }
}

 

标准答案:

  

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j,因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

 

标签:977,平方,nums,int,res,vector,数组,size
From: https://www.cnblogs.com/lihaoxiang/p/16939362.html

相关文章

  • js如何判断两个数组是否有重复的元素
    原文:https://www.yisu.com/zixun/730087.htmljs如何判断两个数组是否有重复的元素leta=[1,2,3];letb=[3,5,2];newA=newSet(a);newB=newSet(b);letin......
  • 数组相关
    冒泡排序相邻元素两两比较,如果第一个比第二个大就交换位置每一次比较,都会产生一个最大或最小的数字下一轮可以少一次排序时间复杂度O(n2)//临时变量inttemp=0;//外......
  • 清点人数-树状数组
    这题我用了两种方法,都超时,最后百度一个出来.....,上传两个代码,第一个代码是网上查的,那三个函数表示有点不懂,求解答!描述初始时,火车上没有学生;当同学们开始上火车时,年级主任从......
  • Context 是如何影响 grpc 通信超时控制的 行扩容且扩容后的元素数量超过原始切片容量
    Golang中那些隐秘的角落https://mp.weixin.qq.com/s/p572g5KcSwy2ri40d1cPTgGolang中那些隐秘的角落原创 张千风(千风) 阿里开发者 2022-11-3009:00 发表于北京......
  • js 字符串转数组,数组解构默认值 All In One
    js字符串转数组,数组解构默认值AllInOnebug❌const[year,month,day,title]=[1,2];year;//1day;//undefinedsolution✅const[year='a1',month='a......
  • 数组
    数组常见操作遍历,指的就是“通过循环遍历数组的所有元素”。拷贝,指的是将某个数组的内容拷贝到另一个数组中。注:实质上,后面大家学容器的扩容就是“数组的拷贝”。......
  • 13个你必须知道的JS数组技巧
    英文| https://dev.to/duomly/13-useful-javascript-array-tips-and-tricks-you-should-know-2jfo​在Javascript中,数组是一个重要且常见的知识点,我们经常将数据存储在数......
  • 12种解决数组去重的方案
    兜个小圈先总结一下我们数组的方法:poppushshiftunshiftslicesplicesortreverseconcotjoinindexOflastIndexOfmapforEach还有其他可以处理数组的几个方法~–includes:返回一......
  • JS 将伪数组转换成数组
    在 ​​JS​​ 中,伪数组 是非常常见的,它也叫 类数组。伪数组可能会给 ​​JS​​ 初学者带来一点困扰。本文将详细讲解 什么是伪数组,以及分别在 ​​ES5​​ 和 ......
  • 稀疏数组
    publicclassArrayDemo03{//稀疏数组publicstaticvoidmain(String[]args){//1.创建一个二维数组11*110:没有棋子1:黑棋2:白旗int[]......