代码随想录二刷 | 数组 | 有序数组的平方
代码随想录二刷 | 数组 | 有序数组的平方
- 题目描述
- 题目分析 & 代码实现
- 暴力排序
- 双指针法
题目描述
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 已按 非递减顺序 排序
进阶:
请你设计时间复杂度为 O(n) 的算法解决本问题
题目分析 & 代码实现
暴力排序
每个数平方之后再排序
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;}
};
时间复杂度:O(n + nlogn)
双指针法
题目中说数组是非递减排序,需要注意的是负数平方之后可能成为最大值,因此数组平方后的最大值一定出现在最左侧或最右侧。
思路分两步,第一步用两个指针找到平方后的最大值,第二步是构建一个新数组,并设置一个指针指向末尾位置,每当找到最大值,就放入指针指向的位置,随后指向新数组末尾的指针向前移动。直至 i <= j。
详细如下:
设置一个指针 i 指向初始位置,指针 j 指向末尾位置。
定义一个与数组 A 一样大的新数组 result,让指针 k 指向 result 数组的末尾位置。
如果A[i] * A[i] < A[j] * A[j],那么result[k--] = A[j] * A[j]
如果A[i] * A[i] >= A[j] * A[j],那么result[k--] = A[i] * A[i]
class Solution {
public:vector<int> sortedSquares(vector<int> &A) {int k = A.size() - 1;vector<int> result(A.size(), 0); // 构建一个新数组,长度与A相同,用0填充// i 指向初始位置,j 指向末尾位置,直到 i <= j时结束for (int i = 0, j = A.size() - 1; i <= j) { if (A[i] * A[i] >= A[j] * A[j]) {result[k--] = A[i] * A[i];i++; // A[i]的平方已经是最大值,需要移动 i 指针} else {result[k--] = A[j] * A[j];j--; // A[j]的平方已经是最大值,需要移动 j 指针}}return result;}
};
相关文章:
代码随想录二刷 | 数组 | 有序数组的平方
代码随想录二刷 | 数组 | 有序数组的平方 题目描述题目分析 & 代码实现暴力排序双指针法 题目描述 977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 …...
基于单片机C51全自动洗衣机仿真设计
**单片机设计介绍, 基于单片机C51全自动洗衣机仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机C51的全自动洗衣机仿真设计是一个复杂的项目,它涉及到硬件和软件的设计和实现。以下是对这…...
「Verilog学习笔记」实现3-8译码器①
专栏前言 本专栏的内容主要是记录本人学习Verilog过程中的一些知识点,刷题网站用的是牛客网 分析 ① 本题要求根据38译码器的功能表实现该电路,同时要求采用基础逻辑门实现,那么就需要将功能表转换为逻辑表达式。 timescale 1ns/1nsmodule d…...
Centos(Linux)服务器安装Dotnet8 及 常见问题解决
1. 下载dotnet8 sdk 下载 .NET 8.0 SDK (v8.0.100) - Linux x64 Binaries 拿到 dotnet-sdk-8.0.100-linux-x64.tar.gz 文件 2. 把文件上传到 /usr/local/software 目录 mkdir -p /usr/local/software/dotnet8 把文件拷贝过去 mv dotnet-sdk-8.0.100-linux-x64.tar.gz /usr/loc…...
最强人工智能ChatGPT引领AIGC发展
从公众号转载,关注微信公众号掌握更多技术动态 --------------------------------------------------------------- ——AI不会淘汰所有人,但会淘汰不懂AI的人 一、最强人工智能GPT-4 Turbo 在前不久的OpenAI开发者大会,正值Chatgpt3.5发布一…...
10.Oracle的同义词与序列
oracle11g的同义词与序列 一、Oracle同义词:1、同义词的基本使用2、同义词的相关权限3、同义词的作用范围 二、Oracle序列:1、序列的基本操作2、序列的相关权限 一、Oracle同义词: 同义词是一个数据库对象的别名,它允许用户通过不…...
【周报2023-11-10】
周报2023-11-10 本周的主要工作下周工作计划 本周的主要工作 本周的主要工作就有三个 第一个是进行对我们目前的高企项目的完善情况第二个是对于高企项目的接口对接情况以及细节的把控第三个为新的小程序项目做准备工作 首先第一个高企项目的完善情况得话主要是页面上 对于原…...
搜维尔科技:业内普遍选择Varjo头显作为医疗VR/AR/XR解决方案
Varjo 的人眼分辨率混合现实和虚拟现实头显将医疗专业人员的注意力和情感投入提升到更高水平。借助逼真的 XR/VR,医疗和保健人员可以为最具挑战性的现实场景做好准备! 在虚拟、增强和混合现实中进行最高水平的训练和表现 以逼真的 3D 方式可视化医疗数据…...
数据结构02附录01:顺序表考研习题[C++]
图源:文心一言 考研笔记整理~🥝🥝 之前的博文链接在此:数据结构02:线性表[顺序表链表]_线性链表-CSDN博客~🥝🥝 本篇作为线性表的代码补充,每道题提供了优解和暴力解算法…...
ClientDateSet:Cannot perform this operation on a closed dataset
一、问题表现 Delphi 三层DataSnap,使用AlphaControls控件优化界面,一窗口编辑时,出现下列错误提示: 编译通过,该窗口中,重新显示数据,下图: 相关代码: procedure…...
python中列表的基础解释
列表: 一种可以存放多种类型数据的数据结构 列表的创建: 1.用【】创建列表 #创建一个空列表 list1[] #创建一个非空列表 list2 [zhang,li,ying,1,2,3] #输出内容及类型 print(list1,type(list1)) print(list2,type(list2))结果: 2.使用list…...
『力扣刷题本』:链表分割
一、题目 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。 二、思路解析 首先,让我们列出我们需要做的事情&…...
FISCOBCOS入门(十)Truffle测试helloworld智能合约
本文带你从零开始搭建truffle以及编写迁移脚本和测试文件,并对测试文件的代码进行解释,让你更深入的理解truffle测试智能合约的原理,制作不易,望一键三连 在windos终端内安装truffle npm install -g truffle 安装truffle时可能出现网络报错,多试几次即可 truffle --vers…...
Unity Text文本首行缩进两个字符的方法
Text文本首行缩进两个字符的方法比较简单。通过代码把"\u3000\u3000"加到文本字符串前面即可。 参考如下代码: TMPtext1.text "\u3000\u3000" "这是一段有首行缩进的文本内容。\n这是第二行"; 运行效果如下图所示: 虽…...
TS的函数重载、类型合并、类型断言
函数重载 let list5 [1, 2, 3, 4]function findNum(id: number): number[]function findNum(): number[]function findNum(list: number[]): number[]function findNum(ids?: number | number[]): number[] {if (typeof ids number) {return list5.filter((num) > num …...
JVM:字节码文件,类的生命周期,类加载器
JVM:字节码文件,类的生命周期,类加载器 为什么要学这门课程 1. 初识JVM1.1. 什么是JVM1.2. JVM的功能1.3. 常见的JVM 2. 字节码文件详解2.1. Java虚拟机的组成2.2. 字节码文件的组成2.2.1. 以正确的姿势打开文…...
【IPC】消息队列
1、IPC对象 除了最原始的进程间通信方式信号、无名管道和有名管道外,还有三种进程间通信方式,这 三种方式称之为IPC对象 IPC对象分类:消息队列、共享内存、信号量(信号灯集) IPC对象也是在内核空间开辟区域,每一种IPC对象创建好…...
内网穿透工具NPS(保姆级教程)
前言: 有时候我们受限于硬件设备和网络的的问题,无法将内网的大容量、高性能存储设备或计算设备对外访问。这个时候就会变的特别苦恼,上云呢成本太大,不用云呢公网又无法直接访问,这个时候怎么办呢,NPS它来…...
最长公共子序列问题
构造最长公共子序列为什么要这样构造序列 for(int i1;i<n;i){int k;cin>>k;b[k]i;}for(int i1;i<n;i){int k;cin>>k;a[i]b[k];}并且为什么要求上升序列,是有什么数学知识包含在其中吗? 为什么在求最长公共子序列时,f[mid]大…...
服务器数据恢复—热备盘同步中断导致Raid5数据丢失的数据恢复案例
服务器数据恢复环境: 某单位一台服务器上有一组raid5阵列,该raid5阵列有15块成员盘。上层是一个xfs裸分区,起始位置是0扇区。 服务器故障&检测: 服务器raid5阵列中有硬盘性能表现不稳定,但是由于管理员长时间没有关…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
