• 首页

  • 文章归档

  • 文章分类

  • 日志

  • 图库

  • 友链

  • 留言板

  • 关于我
H i , m e g u m i
H i , m e g u m i

无名高

获取中...

10
16
算法题

LeetCode 977.有序数组的平方

发表于 2020-10-16 • leetcode 双指针 • 被 106 人看爆

题目描述:
image.png

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


思路:
最容易想到的方法就是先平方再排序,这样时间复杂度O(nlogn)

但是这题有A的非递减特性可以利用,非负数的平方还是一个非递减顺序,负数的平方是一个非递增序列,将其逆序就是非递减序列了。于是可以先找到非负数和负数的分界线,然后使用双指针依次比较非负数和负数平方后的数值,填入较小的数值,指针后移。
然后注意双指针的边界条件即可。
时间复杂度是O(n),我使用一个临时数组存储了序列平方后的数值,空间复杂度O(n)。因为个人觉得如果每次都将数平方比较的话,乘法运算耗时较长,所以使用了临时数组。

代码:

class Solution {
private:
    vector<int> ans;
public:
    
    /**
     给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。
     **/
    vector<int> sortedSquares(vector<int>& A) {
        
        // 找到数组中非负数和负数的分界位置
        int i = 0; // i指向非负数的第一个位置
        while (i <= A.size()-1) {
            if (A[i] < 0) {
                ++i;
            }else break;
        }
        int size = (int)A.size();
        if (i == A.size()) {// 没有非负数,即全是负数,则其平方逆序即可
            ans.resize(A.size());
            
            for (int i = 0; i < A.size(); ++i) {
                ans[size-1-i] = A[i]*A[i];
            }
        }else{
            // 存在非负数,需要对平方后的逆序和正序序列归并排序
            vector<int> tmp;
            tmp.resize(size);
            for (int k = 0; k < A.size(); ++k) {
                tmp[k] = A[k]*A[k];
            }
            int left = i-1, right = i;
            while (left >= 0 && right < size) {
                if (tmp[left] <= tmp[right]) {
                    ans.push_back(tmp[left]);
                    --left;
                }else{
                    ans.push_back(tmp[right]);
                    ++right;
                }
            }
            
            while (left >= 0) {
                ans.push_back(tmp[left]);
                --left;
            }
            
            while (right < size) {
                ans.push_back(tmp[right]);
                ++right;
            }
        }
        return ans;
    }
};
分享到:
LeetCode 234.回文联表
计算机网络——网络层(四)
  • 文章目录
  • 站点概览
无名高

帅哥无名高

我们是如何走到这一步

Github QQ Email RSS
看爆 Top5
  • SpringBoot学习笔记 411次看爆
  • JDBC核心技术笔记 335次看爆
  • SpringMVC学习笔记 274次看爆
  • 解决在IDEA编写Java代码时,向数据库中插入中文字符后显示?乱码问题 267次看爆
  • Linux安装zookeeper 237次看爆
粤公网安备 44030702003128号
本站总访问量次 本站访客数人次

Copyright © 2021 无名高 · 黔ICP备20006240号

Proudly published with Halo · Theme by fyang · 站点地图