专栏首页刷题笔记【LeetCode】977. Squares of a Sorted Array数组 双指针

【LeetCode】977. Squares of a Sorted Array数组 双指针

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2:

Input: [-7,-3,2,3,11] Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array

跟刚才那道题很像,找到一个神奇思路,两边的平方一定是最大的,so~双指针从两边往中间移动就很简单了,一开始从中间往两边走就麻烦很多

但是这个时间速度很慢~百分之23%

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n=A.size();
        vector<int> num(n);
        if(n==0){
            return num;
        }
        int a=0;
        int b=n-1;
        int na,nb;
        while(n>0&&a!=b){
            n--;
            na=A[a]*A[a];
            nb=A[b]*A[b];
            if(na>nb){
                a++;
                num[n]=na;
            }else{
                b--;
                num[n]=nb;
            }
        }
        if(n>0) num[0]=A[a]*A[a];
        return num;
    }
};

暴力的老哥都比我快

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        //暴力求解 双指针
        int start =0,end=A.size()-1;
        vector<int> res;
        while(start<=end){
            if(abs(A[start])>abs(A[end])){
                res.push_back(A[start]*A[start]);
                start++;
            }else{
                res.push_back(A[end]*A[end]);
                end--;
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1052 卖个萌 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【未完成】7-8 最长有效括号串 (20 分)13分

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • 【LeetCode】221. 最大正方形

    在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

    韩旭051
  • 【Leetcode】【python】Array Partition I, Number Complement

    可以看到答案使用了sorted()以及切片,值得学习。尤其是切片,我平常不怎么用。

    后端技术漫谈
  • leetcode 32 Longest Valid Parentheses

    @坤的
  • BZOJ4636: 蒟蒻的数列(动态开节点线段树)

    attack
  • 1038. 统计同成绩学生(20)

    输入在第1行给出不超过105的正整数N,即学生总人数。随后1行给出N名学生的百分制整数成绩,中间以空格分隔。最后1行给出要查询的分数个数K(不超过N的正整数),...

    AI那点小事
  • Android自定义组合控件---教你如何自定义下拉刷新和左滑删除

    版权声明:本文为博主原创文章,转载请标明出处。 https://blog.csdn.net/lyhhj/article/details/80...

    Hankkin
  • python基础学习1

      1. 字母数字下划线组成   2. 不能以数字开头,不能含有特殊字符和空格   3. 不能以保留字命名   4. 不能以中文命名   5. 定义的变量名应该...

    py3study
  • 【模板小程序】非负数2~62任意进制转换(普通版本+大数版本)

    再来一个针对大数的版本,而且直接在源进制和目标进制之间转换(不需要先转换为10进制),可以说是十分厉害。参考了http://blog.csdn.net/jast...

    xiaoxi666

扫码关注云+社区

领取腾讯云代金券