算法第六天:力扣第977题有序数组的平方

一、977.有序数组的平方的链接与题目描述

977. 有序数组的平方的链接如下所示:https://leetcode.cn/problems/squares-of-a-sorted-array/description/icon-default.png?t=N7T8https://leetcode.cn/problems/squares-of-a-sorted-array/description/

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

    提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

    进阶:

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

二、977.有序数组的平方的c++代码: 

   第一种方法:双指针的时间复杂度o(n),具体代码如下:

        vector<int> result(nums.size(), 0);int n=nums.size()-1;int left=0, right=n;while(left<=right){if(pow(nums[left], 2)>pow(nums[right], 2)){result[n--]=pow(nums[left], 2);left++;}else{result[n--]=pow(nums[right], 2);right--;}}return result;

    第二种方法:快速排序的时间复杂度o(nlogn) ,具体代码如下:

        for(int i=0;i<=nums.size()-1;i++){nums[i]*=nums[i]; //快速排序}sort(nums.begin(), nums.end());return nums;

三、解题思路

    本题主要讲解双指针的算法思路,下面的本题的4个步骤:

  1. 定义左指针的索引值为0,右指针为nums.size()-1,容器result装平方后的数组元素;
  2. 用while判断条件,如果左指针的值小于等于右指针的值,则循环继续,反之,则终止;
  3. 判断数组开始的值的平方是否大于末尾的值的平方,如果大于,输入result[n--]=pow(nums[left], 2); left++,反之,则result[n--]=pow(nums[right], 2); right--;
  4. 最后输出result,得出答案。

    感谢各位读者的阅读与支持,您的支持是我前进的动力!我希望我的博文能够带给您双指针的一些算法知识和启发。如果您有任何问题或意见,请随时联系我或在评论区评论。希望本题的算法知识对大家有帮助,谢谢各位读者的支持!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/353975.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 部门组队编程(200分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f…

ArcGIS for js 4.x FeatureLayer 点选查询

示例&#xff1a; 代码如下&#xff1a; <template><view class"map" id"mapView"></view></template><script setup> import "arcgis/core/assets/esri/themes/light/main.css"; import Map from "arcgis/…

没有名为 keras.preprocessing 的模块

估计是因为版本原因 我安装的是 3.3.3版本 >>> import keras >>> print(keras.__version__) 3.3.3 keras.preprocessing.image 将 keras.preprocessing.image 改为 from keras_preprocessing.image 之后报image_type啥的错误&#xff0c;后面查找之后…

使用vscode插件du-i18n处理前端项目国际化翻译多语言

前段时间我写了一篇关于项目国际化使用I18n组件的文章&#xff0c;Vue3 TS 使用国际化组件I18n&#xff0c;那个时候还没真正在项目中使用&#xff0c;需求排期还没有定&#xff0c;相当于是预研。 当时就看了一下大概怎么用&#xff0c;改了一个简单的页面&#xff0c;最近需…

qt事件和连接TCP协议

QT网络聊天室服务器实现 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget),server(new QTcpServer(this))//给服务器指针实例化一个空间 {ui->setupUi(this); }Widget::~Widget() {d…

python Django安装及怎么检测是否安装成功

一、winr 输入cmd 进入控制台。输入pip install Django5.0.1 二、如果安装过程没有问题。就进行下一步进行检查是否成功安装。 三、 1.在控制台输入python&#xff0c;进入python环境 2.输入 import django 3.继续输入 django.get_version()。显示版本号表示成功安装。

MySQL8,Navicat能登陆成功,密码却忘记了

执行成功的图&#xff1a; 以下为步骤&#xff1a;本文一共8个简单步骤。 环境&#xff1a;mysql8、window10、navicat11 1、打开本地电脑window10的命令窗&#xff08;俗称黑窗口&#xff09;&#xff0c;windowR 2、输入regegit&#xff0c;回车&#xff0c;打开注册表 3、…

揭开AI大模型的神秘面纱:一文看懂GPT-4的核心技术

近年来&#xff0c;人工智能&#xff08;AI&#xff09;技术迅猛发展&#xff0c;特别是AI大模型的崛起&#xff0c;给人们的生活和工作带来了深远的影响。作为其中的佼佼者&#xff0c;GPT-4备受瞩目。那么&#xff0c;GPT-4的核心技术究竟是什么&#xff1f;它是如何运作的&a…

win10远程桌面端口,win10操作系统怎么修改远程桌面端口和共享端口号

在Win10操作系统中&#xff0c;远程桌面端口和共享端口号的修改是两项重要的网络配置任务&#xff0c;它们对于提升系统的安全性和灵活性具有重要意义。以下将分别介绍如何在Win10中修改这两个端口号。 一、Win10操作系统远程桌面端口的修改 远程桌面端口的修改主要涉及到注册…

【毕业设计】Django 校园二手交易平台(有源码+mysql数据)

此项目有完整实现源码&#xff0c;有需要请联系博主 Django 校园二手交易平台开发项目 项目选择动机 本项目旨在开发一个基于Django的校园二手交易平台&#xff0c;为大学生提供一个安全便捷的二手物品买卖平台。该平台将提供用户注册和认证、物品发布和搜索、交易信息管理等…

【C++高阶】高效搜索的秘密:深入解析搜索二叉树

&#x1f4dd;个人主页&#x1f339;&#xff1a;Eternity._ ⏩收录专栏⏪&#xff1a;C “ 登神长阶 ” &#x1f921;往期回顾&#x1f921;&#xff1a;C多态 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; ❀二叉搜索树 &#x1f4d2;1. 二叉搜索树&…

Java——构造器(构造方法)和 this

一、什么是构造器 构造器&#xff08;Constructor&#xff09;是Java类的一种特殊方法&#xff0c;用于初始化对象的状态。构造器在创建对象时被调用&#xff0c;可以对对象的成员变量进行初始化。 我之前的文章《Java——类和对象-CSDN博客》中也提到了构造器。 二、构造器…

银行数仓项目实战(四)--了解银行业务(存款)

文章目录 项目准备存款活期定期整存整取零存整取存本取息教育储蓄定活两便通知存款 对公存款对公账户协议存款 利率 项目准备 &#xff08;贴源层不必写到项目文档&#xff0c;因为没啥操作没啥技术&#xff0c;只是数据。&#xff09; 可以看到&#xff0c;银行的贴源层并不紧…

【两数之和】

两数之和 一、题目二、暴力解法三、哈希表四、map字典1.基本方法.set()添加键值对.get()通过键获取值.has()判断map是否有这个键 2.map和set的联系和区别共同点共同点MapSet 一、题目 二、暴力解法 三、哈希表 解题思路&#xff1a;将nums的元素依次以键值对的方式存储在map字典…

java 线程之间通信-volatile 和 synchronized

你好&#xff0c;我是 shengjk1&#xff0c;多年大厂经验&#xff0c;努力构建 通俗易懂的、好玩的编程语言教程。 欢迎关注&#xff01;你会有如下收益&#xff1a; 了解大厂经验拥有和大厂相匹配的技术等 希望看什么&#xff0c;评论或者私信告诉我&#xff01; 文章目录 一…

python学习笔记-08

面向对象基础(OOP)-上 1. 面向对象概述 面向过程&#xff1a;根据业务逻辑从上到下写代码 函数式&#xff1a;将某功能代码封装到函数中&#xff0c;日后便无需重复编写&#xff0c;仅调用函数即可 面向对象(object oriented programming)&#xff1a;将数据与函数绑定到一起…

通过Vue3+高德地图的JS API实现市区地图渲染

效果图1: 核心代码1: <script setup>import { onMounted, onUnmounted } from vue;import AMapLoader from @amap/amap-jsapi-loader;import { message } from ant-design-vue;import school from @/assets/icons/school.svg;import enterprise from @/assets/icons/e…

laravel版本≥ 8.1

laravel10 php ≥ 8.1 且 ≤ 8.3&#xff1f; 8.1 < php < 8.3PHP版本要求在 8.1 到 8.3 之间&#xff0c;包括这两个版本。具体来说&#xff1a;"≥ 8.1" 表示 PHP 的版本至少是 8.1&#xff0c;也就是说 8.1 及以上的版本都可以。 "≤ 8.3" 表示 P…

3dmax怎么渲染又快又清晰?

在3ds Max中&#xff0c;追求快速且清晰的渲染效果是每个设计师的目标。云渲染技术的出现&#xff0c;为这一目标提供了强大的支持。通过云渲染&#xff0c;设计师能够利用远程服务器的强大计算能力&#xff0c;实现快速渲染&#xff0c;同时保持图像的高清晰度。 一、3dmax怎么…

C++ 75 之 异常的传递

#include <iostream> #include <string> using namespace std;// 1.自己准备好一个类&#xff0c;写自己要打印的内容 class MyException{ public:void printE(){cout << "我自己写的异常" << endl;} };class Students02{ public:Students02…