【代码随想录】有序数组的平方

本博文为《代码随想录》的学习笔记,原文链接:代码随想录

题目

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) 的算法解决本问题

题解

为适应机试环境,首先在Dev C++中编写程序

输入输出说明:

输入:数组元素个数n,数组nums元素

输出:平方并排序后数组

示例一:

输入:5 -4 -1 0 3 10
输出:0 1 9 16 100

示例二:

输入:5 -7 -3 2 3 11
输出:4 9 9 49 121

方法一:暴力求解

使用sort()函数对平方后的数组元素进行排序。

在Dev C++中编译

#include <bits/stdc++.h>
using namespace std;vector<int> sortedSquares(vector<int>& nums)
{int length=nums.size();vector<int> square;for(int i=0;i<length;i++){int ans=nums[i]*nums[i];square.push_back(ans);}sort(square.begin(), square.end());return square;
}
int main()
{int n;	cin>>n;vector<int>nums;for(int i=0;i<n;i++){int ans;cin>>ans;nums.push_back(ans);}vector<int> nums2 = sortedSquares(nums); // 调用你的实现for(int i=0;i<nums2.size();i++){cout<<nums2[i]<<" ";}return 0;
}

运行结果:

在LeetCode中运行

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int length = nums.size();vector<int> square;for (int i = 0; i < length; i++) {int ans = nums[i] * nums[i];square.push_back(ans);}sort(square.begin(), square.end());return square;}
};

这个时间复杂度是 O(n + nlogn), 可以说是O(nlogn)的时间复杂度,但为了和下面双指针法算法时间复杂度有鲜明对比,我记为 O(n + nlog n)。

方法二:双指针法

题目关键词:非递减顺序 排序的整数数组 nums

数组其实是有序的,只不过负数平方后可能成为最大数了。

那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。

此时可以考虑双指针法,i指向起始位置,j指向终止位置。

定义一个新数组result,和A数组一样的大小,让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];

如动画所示:

在Dev C++中编译

#include <bits/stdc++.h>
using namespace std;vector<int> sortedSquares(vector<int>& nums)
{int k=nums.size()-1;int length=nums.size();vector<int> square(nums.size(),0);for(int i=0, j=length-1;i<=j;)//注意这里的写法{if(nums[i]*nums[i]<=nums[j]*nums[j]){square[k--]=nums[j]*nums[j];j--;}else{square[k--]=nums[i]*nums[i];i++;}}return square;
}
int main()
{int n;	cin>>n;vector<int>nums;for(int i=0;i<n;i++){int ans;cin>>ans;nums.push_back(ans);}vector<int> nums2 = sortedSquares(nums); // 调用你的实现for(int i=0;i<nums2.size();i++){cout<<nums2[i]<<" ";}return 0;
}

在LeetCode中运行

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int k = nums.size() - 1;int length = nums.size();vector<int> square(nums.size(), 0);for (int i = 0, j = length - 1; i <= j;) {if (nums[i] * nums[i] <= nums[j] * nums[j]) {square[k--] = nums[j] * nums[j];j--;} else {square[k--] = nums[i] * nums[i];i++;}}return square;}
};

此时的时间复杂度为O(n),相对于暴力排序的解法O(n + nlog n)还是提升不少的。 

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

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

相关文章

【物联网设备端开发】使用QEMU模拟ESP硬件运行ESP-IDF

目录 一&#xff0c;开发环境搭建 1.1 安装ESP-IDF 1.2 安装vscode插件 1.3 在ESP-IDF插件配置ESP-IDF开发配置 1.4 下载IOTDeviceSDK 设备端开发代码 1.5 通过ESP-IDF插件编译好镜像 1.6 构建QEMU docker镜像 1.7 使用QEMU容器运行镜像 二&#xff0c;搭建QEMU环境步…

PTrade常见问题系列22

反馈定义的上午7点执行run_daily函数&#xff0c;但是每周一上午都没法正常执行&#xff1f; 1、run_daily函数加载在initialize函数中&#xff0c;执行后才会创建定时任务&#xff1b; 2、由于周末会有例行重启操作&#xff0c;在重启以后拉起交易时相当于非交易日启动的交易…

C到C++——C++基础

C是一种通用的、静态类型的、跨平台的编程语言。它是在1979年由Bjarne Stroustrup创建的&#xff0c;最初是作为C语言的扩展来支持面向对象编程。 C在保留C语言的特性的同时&#xff0c;添加了许多其他的功能&#xff0c;包括类、对象、继承、多态、模板等。这使得C成为了一种…

大数据面试SQL(五):查询最近一笔有效订单

文章目录 查询最近一笔有效订单 一、题目 二、分析 三、SQL实战 四、样例数据参考 查询最近一笔有效订单 一、题目 现有订单表t5_order&#xff0c;包含订单ID&#xff0c;订单时间&#xff0c;下单用户&#xff0c;当前订单是否有效。 请查询出每笔订单的上一笔有效订…

Vue - 关于vue-kinesis 移动动画组件

Vue - 关于vue-kinesis 移动动画组件 vue-kinesis可以根据鼠标移动或滚动条来控制元素动画的动画效果&#xff1b;除此之外&#xff0c;vue-kinesis 还可以设置音频文件&#xff0c;根据音频频率来控制动画的跳动效果。 一、安装vue-kinesis Vue2版本&#xff1a; 1.安装 …

2024.8.08(python)

一、搭建python环境 1、检查是否安装python [rootpython ~]# yum list installed | grep python [rootpython ~]# yum list | grep python3 2、安装python3 [rootpython ~]# yum -y install python3 安装3.12可以使用源码安装 3、查看版本信息 [rootpython ~]# python3 --vers…

数字信号处理2: 离散信号与系统的频谱分析

文章目录 前言一、实验目的二、实验设备三、实验内容四、实验原理五、实验步骤1.序列的离散傅里叶变换及分析2.利用共轭对称性&#xff0c;设计高效算法计算2个N点实序列的DFT。3.线性卷积及循环卷积的实现及二者关系分析4.比较DFT和FFT的运算时间5.利用FFT求信号频谱及分析采样…

游戏行业最新报告 | 2024年1—6月:中国游戏市场收入上升至1472.67亿元

2024年1—6月收入&#xff1a;达1472.67亿元&#xff0c;同比增长2.08% 伽马数据提供的数据显示&#xff1a;2024年1—6月&#xff0c;国内游戏市场实际销售收入1472.67亿元&#xff0c;同比增长2.08%&#xff0c;增长趋势较为平稳。 中国市场实际销售收入及增长率 游戏用户达…

(24)(24.2) Minim OSD快速安装指南(一)

文章目录 前言 1 概述 2 基本接线图 3 关键冷却条件的可选设置 4 固件可用于MinimOSD 5 MWOSD 前言 MinimOSD “屏幕显示”是一个小型电路板&#xff0c;它从你的自动驾驶仪中提取遥测数据&#xff0c;并将其覆盖在你的第一人称视图监视器上(First Person View)。Minim …

极限挑战:40亿个非负整数中找到没有出现的数(bit数组)

我是小米,一个喜欢分享技术的29岁程序员。如果你喜欢我的文章,欢迎关注我的微信公众号“软件求生”,获取更多技术干货! 大家好!我是小米,一个积极活泼、热爱分享技术的29岁程序员。今天,我们一起来探讨一个有趣且实用的算法问题:如何在40亿个非负整数中找到没有出现的数…

Powershell 禁用系统更新

创建一个关闭系统更新脚本 脚本系统兼容10,11,2012,206,2019,2022,2025powershell-install-stop-System-update.ps1 <# Powershell Install stop System update +++++++++++++++++++++++++++++++++++++++++++++++++++++ + _____ _____ _ …

供应商较多的汽车制造业如何选择供应商协同平台?

汽车制造业的供应商种类繁多&#xff0c;根据供应链的不同环节和产品特性&#xff0c;可以大致分为以下几类。 按供应链等级分包括&#xff1a; 一级供应商通常具有较高的技术水平和生产能力&#xff0c;能够满足汽车厂商对零部件的高品质、高性能和高可靠性的要求。 二级供应…

ImportError: DLL load failed while importing _rust: 找不到指定的程序的解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

【Android Studio】Webview 内核升级得三种方法

【Android Studio】Webview 内核升级得三种方法 前言X5 腾讯组件crosswalk开源项目webview升级加载的内核&#xff08;完美解决&#xff09;总结 前言 在APP 中进行网页加载&#xff0c;一般采用原生自带的Webview 组件&#xff0c;但在需要加载高版本网页的时候&#xff0c;有…

【CSS入门】第三课 - padding内填充

上一节&#xff0c;我们说了margin外边距&#xff0c;还举了个例子&#xff0c;比如两个人紧挨着站着&#xff0c;如果两个人冬天穿了棉袄&#xff0c;很厚很厚的棉袄&#xff0c;那么他俩占据的空间就会增加&#xff0c;他俩之间的真实距离也会增加。 这一节&#xff0c;我们…

《暗黑破坏神 IV》是什么类型的游戏,苹果电脑能玩暗黑破坏神吗 crossover玩暗黑4

《暗黑破坏神 IV》&#xff08;Diablo IV&#xff09;是由暴雪娱乐开发的一款动作角色扮演游戏&#xff08;Action RPG&#xff09;&#xff0c;是广受欢迎的《暗黑破坏神》系列的最新作品。暗黑破坏神4拥有出色的游戏画面、音效和丰富的游戏玩法&#xff0c;非常值得玩家们去尝…

SpringBoot3热部署

引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-devtools</artifactId><scope>runtime</scope><optional>true</optional> </dependency> 默认就是,无需配置 可以了…

ADB Installer 0 file(s)copied

在为泡面神器刷安卓&#xff0c;做准备工作装ADB时报错了&#xff0c;以下是报错提示 再用cmd命令adb version验证下&#xff0c;提示adb不是有效命令&#xff0c;百分百安装失败了&#xff0c;往上各种搜索查询均没有对症的&#xff0c;其中也尝试了安装更新版本的&#xff0c…

翻译: 可视化深度学习反向传播原理一

本期我们来讲反向传播 也就是神经网络学习的核心算法 稍微回顾一下我们之前讲到哪里之后 首先我要撇开公式不提 直观地过一遍 这个算法到底在做什么 然后如果你们有人想认真看里头的数学 下一期影片我会解释这一切背后的微积分 如果你看了前两期影片 或者你已经有足够背景知…

牛羊肉巨头的数字化战略:凯宇星辉如何领先市场

凯宇星辉的创业成长史&#xff0c;给出了中国牛羊肉企业如何从散户走向集团化经营的路线图。 总部位于大连的凯宇星辉&#xff0c;在牛羊肉进口贸易领域白手起家&#xff0c;十余年时间&#xff0c;已形成以澳新、南美、北美等全球三大牛羊肉主产区为主渠道的全球直采网络布局…