当前位置: 首页 > news >正文

【代码随想录-Leetcode第三题:977. 有序数组的平方】

题目

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

思路

方法一: 先求解,再排序。

class Solution {
public:vector<int> sortedSquares(vector<int>& A) {for (int i = 0; i < A.size(); i++) {A[i] *= A[i];}sort(A.begin(), A.end()); // 快速排序return A;}
}

方法2:牺牲空间来换取时间复杂度:
思路:既然起始时顺序是排好的,只不过第一个位置的负的元素可能平方后可能是最大的,也有可能是最后一个元素的平方后是最大的,要排在最后。既然这样,最大的数排在最后或者开头(负数),因此不会在中间。

1、定义一个新的数组result用来结果,定义一个变量k指向result最后一个位置,当有最大的数据筛选出来时,每次把它移入到新数组组中。
2、定义两个“指针”i,j分别指向原数组nums的数组的起始位置和末尾位置。
3、如果num[i]*nums[i]>nums[j]*nums[j]时,说明起始位置的元素比较大。将其移入到新元素的末位置中,同时使得k--i++
4、如果num[i]*nums[i]<=nums[j]*nums[j]时,说明起始位置的元素比较小,末尾元素比较大。将其移入到新元素的末位置中,同时使得k--j--;
5、最后返回result数组即可。

代码实现:

//方法2 @i want to 武动乾坤 2023/08/08
class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k=nums.size()-1;//使得k指向result数组最后一个位置vector<int> result(nums.size(),0);//定义result容器for(int i=0,j=nums.size()-1;i<=j;){//i<=j保证最后两个数据也能被比较加入新数组if(nums[i]*nums[i]>nums[j]*nums[j]){//起始位置大result[k--]=nums[i]*nums[i];//注意k--是先赋值再--//等同于result[k]=nums[i];  k--;i++;//指针向后移动}else{result[k--]=nums[j]*nums[j];//注意k--是先赋值再--//等同于result[k]=nums[i]*nums[i];  k--;j--;//指针向前移动}}return result;//返回新的结果集}};

相关文章:

【代码随想录-Leetcode第三题:977. 有序数组的平方】

题目 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&#xff1a;平方后&#xff0c;数组…...

[运维|中间件] Apache APISIX Dashboard部署(持续踩坑更新。。。)

参考文献 Apache APISIX v2.6 官方文档 APISIX、APISIX Dashboard搭建、路由配置及插件使用 安装apisix和apisix-dashboard&#xff0c;访问方式&#xff0c;测试路由转发&#xff0c;反向代理等 文档地址 Dashboard Doc 下载地址 Apache APISIX Dashboard下载地址 部署 …...

Vue中watch监听属性新旧值相同问题解决方案

侦听器 _watch: 作用:可以侦听data和computed中数据的变化. 语法 watch: { "被侦听的属性名" (newVal, oldVal){ } } 监听简单数据类型时可以直接使用,而监听复杂数据类型时,例如当我们只需要监听data或者computed中对象的某个属性时,可以使用字符串的形式进行监听…...

awk案例练习

目录 一、awk练习 1.1筛选ip地址 1.2字段去重 1.3次数统计 1.4统计TCP连接状态 1.5处理字段缺失的数据 1.6筛选给定时间范围内的日志 一、awk练习 1.1筛选ip地址 ifconfig命令查看IP 利用awk进行筛选 ifconfig | awk BEGIN{RS""}NR2{print $6} RS指定输入记…...

Debian 12.1 正式发布

导读Debian 12.1 现已发布&#xff0c;这是对稳定发行版 Debian 12&#xff08;代号 Bookworm &#xff09;的首次更新。本次发布主要增加了安全问题的修正&#xff0c;并对严重问题进行了一些调整。 一些更新内容包括&#xff1a; 妥善处理系统用户的创建&#xff1b;修复 eq…...

neo4j清空数据库

清空所有Person、 Movie节点及其所有关系 MATCH (a:Person), (m:Movie) OPTIONAL MATCH (a)-[r1]-(), (m)-[r2]-() DELETE a,r1,m,r2 查询任意数据 MATCH (n) RETURN n 如果没有&#xff0c; 就说明已经删除成功了 这段代码是用Cypher查询语言编写的&#xff0c;用于清空…...

SpringBoot整合Mybatis-Plus

文章目录 前言一、Mybatis-Plus简介二、框架结构三、SpringBoot整合Mybatis-Plus1.依赖2.配置文件设置 四、前期准备4.1数据库信息4.2dao类4.3pojo类 五、常用注解5.1 TableName(value "")5.2 TableId(value"",type IdType.XXX)5.3 TableField("&qu…...

在langchain中使用自定义example selector

在langchain中使用自定义example selector 简介 在之前的文章中&#xff0c;我们提到了可以在跟大模型交互的时候&#xff0c;给大模型提供一些具体的例子内容&#xff0c;方便大模型从这些内容中获取想要的答案。这种方便的机制在langchain中叫做FewShotPromptTemplate。 如…...

pytest常用执行参数详解

1. 查看pytest所有可用参数 我们可以通过pytest -h来查看所有可用参数。 从图中可以看出&#xff0c;pytest的参数有很多&#xff0c;下面是归纳一些常用的参数&#xff1a; -s&#xff1a;输出调试信息&#xff0c;包括print打印的信息。 -v&#xff1a;显示更详细的信息。 …...

本地项目如何连接git远程仓库

在本地新建项目后&#xff0c;如何连接git远程仓库呢&#xff1f;步骤如下&#xff1a; 第一步&#xff0c; 首先我们在git上新建仓库&#xff0c;设置模板可勾选Readme文件。&#xff08;readme文件的创建是为了介绍所写代码的一些详细信息,为了之后更好的维护。&#xff09;…...

力扣 494. 目标和

题目来源&#xff1a;https://leetcode.cn/problems/target-sum/description/ C题解&#xff08;来源代码随想录&#xff09;&#xff1a;将该问题转为01背包问题。 假设加法的总和为x&#xff0c;那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) target。x …...

Maven-搭建私有仓库

使用NEXUS REPOSITORY MANAGER 3在Windows上搭建私有仓库。 NEXUS REPOSITORY MANAGER 3 是一个仓库管理系统。 下载NEXUS3 官网上是无法下载的,所以网上搜nexus-3.18.1-01-win64就能搜到,下载即可。 安装NEXUS3 下载nexus-3.18.0-01-win64.zip至相应目录下(路径不要有中文)。 …...

PostgreSql 参数配置

一、访问控制参数配置 https://xiaosonggong.blog.csdn.net/article/details/124264877 二、数据库参数配置 2.1 概述 PostgreSQL 的参数配置参数是在 postgresql.conf 文件中集中管理的&#xff0c;类似于 Oracle 的 pfile 文件&#xff0c;除此之外&#xff0c;PostgreSQL…...

【BMC】OpenBMC开发基础2:修改原有程序

修改原有程序 通常情况下我们会需要修改OpenBMC原有的程序来适配我们的项目&#xff0c;本节将介绍一般的流程。 为此首先我们需要了解devtool这个工具&#xff0c;注意它不是前端开发用的那个devtool&#xff0c;而是由OE&#xff08;或者Yocto&#xff1f;&#xff09;提供…...

2012年数学建模竞赛脑卒中发病环境因素分析及干预日期数据处理代码

因四个表格日期数据处理有些复杂&#xff0c;故作此代码一次性处理四组数据&#xff1a; import datetime import pandas as pddef check(string, df, i, num, error_list):if is_valid(pd.to_datetime(string, errorscoerce, format%Y/%m/%d), error_list, i):df.iloc[i, nu…...

Merge和Rebase的区别

Merge 和 Rebase 是 Git 中常用的两种分支整合方式&#xff0c;它们具有不同的工作原理和效果&#xff1a; Merge&#xff08;合并&#xff09; 合并是将两个或多个分支的提交历史合并为一个新的提交。在合并时&#xff0c;Git 会创建一个新的合并提交&#xff0c;将两个分支…...

[RTKLIB]模糊度固定相关问题(二)

文章目录 一、固定模糊度的前置工作1. 做好固定模糊度的准备2. 建立双差模糊度3. 问题与总结 版权声明&#xff1a;本文为原创文章&#xff0c;版权归 Winston Qu 所有&#xff0c;转载请注明出处。 在上一篇文章中&#xff0c;介绍了RTKLIB中manage_amb_LAMBDA()函数&#xff…...

QtAV for ubuntu16.04

下载ubuntu https://releases.ubuntu.com/16.04/ubuntu-16.04.7-desktop-amd64.iso 下载ffmpeg https://ffmpeg.org/download.html 下载QtAV https://github.com/wang-bin/QtAV/releases 更新 sudo apt update 安装库 sudo apt-get install libglu1-mesa-dev freeglut3-dev…...

MFC 文件读写包括字符串的结构体

试过CString char* 写入的都是地址 struct Param{int ID;int index;char val[128]; };vector<Param>ans; UINT count 17; ans.resize(count); FILE* fp; fopen_s(&fp,_T("my.txt"),_T("rb")); if(count ! fread(&ans[0],sizeof(Param),cou…...

在家构建您的迷你聊天Chat gpt

推荐&#xff1a;使用 NSDT场景编辑器 助你快速搭建可编辑的3D应用场景 什么是指令遵循模型&#xff1f; 语言模型是机器学习模型&#xff0c;可以根据句子的前一个单词预测单词概率。如果我们向模型请求下一个单词&#xff0c;并将其递减地反馈给模型以请求更多单词&#xff…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

webpack面试题

面试题&#xff1a;webpack介绍和简单使用 一、webpack&#xff08;模块化打包工具&#xff09;1. webpack是把项目当作一个整体&#xff0c;通过给定的一个主文件&#xff0c;webpack将从这个主文件开始找到你项目当中的所有依赖文件&#xff0c;使用loaders来处理它们&#x…...

表单设计器拖拽对象时添加属性

背景&#xff1a;因为项目需要。自写设计器。遇到的坑在此记录 使用的拖拽组件时vuedraggable。下面放上局部示例截图。 坑1。draggable标签在拖拽时可以获取到被拖拽的对象属性定义 要使用 :clone, 而不是clone。我想应该是因为draggable标签比较特。另外在使用**:clone时要将…...