每日一题 --- 977. 有序数组的平方[力扣][Go]

今天这一题和昨天的知识点是一样的,就是双指针法
题目:

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

在这里插入图片描述

刚开始我的思路:

func sortedSquares(nums []int) []int {f, r := 0, len(nums)-1var arr = []int{}for f <= r {ones := nums[r] * nums[r]twos := nums[f] * nums[f]if ones <= twos {arr = insertHead(arr, twos)f++} else {arr = insertHead(arr, ones)r--}}return arr
}func insertHead(arr []int, n int) []int {arr = append([]int{n}, arr...)return arr
}

结果时间复杂度O(n²),因为头插需要O(n)。
在这里插入图片描述

代码随想录中有O(log(n))的解法,有兴趣的可以去看看。

链接放这里了:代码随想录 (programmercarl.com)

不过咱们还是直接看O(n)的算法实现吧。

// 双指针
func sortedSquares(nums []int) []int {Len := len(nums)f, r := 0, Len-1arr := make([]int, Len)k := rfor k >= 0 {ones := nums[r] * nums[r]twos := nums[f] * nums[f]if ones >= twos {arr[k] = onesr--} else {arr[k] = twosf++}k--}return arr
}

从两头开始标记,指针平方大的先复制再往里走,直到所有值赋完。

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

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

相关文章

STM32 ESP8266模块的曲折探索

这是本文的配套资料&#xff0c;最终工程请参考 新_ESP8266资料\stm32f103成功移植的项目 【免费】stm32f103c8t6esp8266资料资源-CSDN文库 一、等到了ready 产品参数 我使用的是ai-thinker的esp8266-01s&#xff0c;以下为产品规格书 引脚定义&#xff1a; 依据引脚定义&…

专业140+总分410+南京大学851信号与系统考研经验南大电子信息与通信集成,电通,真题,大纲,参考书。

今年分数出来还是有点小激动&#xff0c;专业851信号与系统140&#xff08;感谢Jenny老师辅导和全程悉心指导&#xff0c;答疑&#xff09;&#xff0c;总分410&#xff0c;梦想的南大离自己越来越近&#xff0c;马上即将复试&#xff0c;心中慌的一p&#xff0c;闲暇之余&…

ubuntu 如何使用阿里云盘

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

通讯录的动态实现

文章目录 通讯录的动态实现模块化编程通讯录的框架构建功能的具体实现初始化通讯录添加联系人删除联系人查找联系人修改联系人打印通讯录排序通讯录检查容量并扩容加载通讯录保留通讯录销毁通讯录 完整代码总结 通讯录的动态实现 模块化编程 分文件 不同模块放在不同的文件下 …

XSKY 智能存储,助力“数据要素 X”先进制造

3 月 21-22 日&#xff0c;主题为“突破 智行”的 IMC2024 第七届中国智造数字科技峰会在重庆召开。作为在先进制造领域拥有领先存储解决方案以及众多应用实践的企业&#xff0c;星辰天合受邀参加了此次峰会并荣获大会颁发的“最佳存储解决方案奖”。同时&#xff0c;星辰天合先…

CISP 4.2备考之《安全支撑技术》知识点总结

文章目录 第一节 密码技术第二节 标识和身份鉴别技术第三节 访问控制技术 第一节 密码技术 密码学发展阶段&#xff1a;古典、近代、现代和公钥密码学及特点。 密码系统组成&#xff1a;明文、加密、密钥、解密、密文。 柯克霍夫原则&#xff1a;密钥保密&#xff0c;算法公开…

手撕算法-删除链表的倒数第 N 个结点

描述 思路 快慢指针&#xff0c;快指针先走N步&#xff0c;走不够N步返回空。慢指针和快指针一起走&#xff0c;当快指针到达终点&#xff0c;即快指针为null时&#xff0c;慢指针到达倒数第N个节点。因为要删除倒数第N个&#xff0c;所以要记录之前的节点pre&#xff0c;假设…

思科网络中DHCP中继的配置

一、什么是DHCP中继&#xff1f;DHCP中继有什么用? &#xff08;1&#xff09;DHCP中继是指一种网络设备或服务&#xff0c;用于在不同的子网之间传递DHCP&#xff08;动态主机配置协议&#xff09;消息。DHCP中继的作用是帮助客户端设备获取IP地址和其他网络配置信息&#x…

开源项目ChatGPT-Next-Web的容器化部署(三)-- k8s deployment.yaml部署

一、说在前面的话 有了docker镜像&#xff0c;要把一个项目部署到K8S里&#xff0c;主要就是编写deployment.yaml。 你需要考虑的是&#xff1a; 环境变量服务的健康检测持久化启动命令程序使用的数据源程序使用的配置文件 因为本前端项目比较简单&#xff0c;这里只做一个…

基于springboot+vue+Mysql的“智慧食堂”设计与实现

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

Vue响应式原理全解析

前言 大家好&#xff0c;我是程序员蒿里行。浅浅记录一下面试中的高频问题&#xff0c;请你谈一下Vue响应式原理。 必备前置知识&#xff0c;​​Vue2​​官方文档中​​深入响应式原理​​​及​​Vue3​​官方文档中​​深入响应式系统​​。 什么是响应式 响应式本质是当…

Redis 不再“开源”,对中国的影响及应对方案

Redis 不再“开源”&#xff0c;使用双许可证 3 月 20 号&#xff0c;Redis 的 CEO Rowan Trollope 在官网上宣布了《Redis 采用双源许可证》的消息。他表示&#xff0c;今后 Redis 的所有新版本都将使用开源代码可用的许可证&#xff0c;不再使用 BSD 协议&#xff0c;而是采用…

基于SpringBoot实现WebSocket实时通讯的服务端和客户端

实现功能 服务端注册的客户端的列表&#xff1b;服务端向客户端发送广播消息&#xff1b;服务端向指定客户端发送消息&#xff1b;服务端向多个客户端发送消息&#xff1b;客户端给服务端发送消息&#xff1b; 效果&#xff1a; 环境 jdk&#xff1a;1.8 SpringBoot&#x…

如何确保多人游戏的配对体验快速而顺利

开发人员知道,游戏玩家在玩游戏时最快乐,他们等待进入多人游戏的时间越长,你失去他们的速度就越快。玩家不喜欢在大厅里等待;他们想马上参与行动。这就是为什么优化匹配是关键。 谷歌(Google)和Unity的Open Match等系统正在加速使用自定义逻辑构建匹配器的能力,使开发人…

跳过mysql权限验证来修改密码-GPT纯享版

建议重新配置一遍&#xff0c;弄成功好多次了&#xff0c;每次都出bug&#xff0c;又要重新弄&#xff0c;不是过期就是又登不进去了&#xff0c;我服了 电脑配置MySQL环境&#xff08;详细&#xff09;这个哥们的10min配完&#xff0c;轻轻松松&#xff0c; 旧方法&#xff…

Python-VBA编程500例-015-03(入门级)

飞行棋(Flying Chess)算法是一种搜索算法&#xff0c;主要用于解决图搜索和路径规划问题。它的主要特点是可以“飞跃”到棋盘上任何位置&#xff0c;从而大大减少了搜索的时间和空间复杂度。以下是一些飞行棋算法的实际应用场景&#xff1a; 1、路径规划&#xff1a;在机器人领…

利用Scala与Apache HttpClient实现网络音频流的抓取

概述 在当今数字化时代&#xff0c;网络数据的抓取和处理已成为许多应用程序和服务的重要组成部分。本文将介绍如何利用Scala编程语言结合Apache HttpClient工具库实现网络音频流的抓取。通过本文&#xff0c;读者将学习如何利用强大的Scala语言和Apache HttpClient库来抓取网…

1.6 学Python能干什么,Python的应用领域有哪些

Python能干什么&#xff0c;Python的应用领域 Python 作为一种功能强大的编程语言&#xff0c;因其简单易学而受到很多开发者的青睐。那么&#xff0c;Python 的应用领域有哪些呢&#xff1f; Python 有着非广泛的应用&#xff0c;几乎所有大中型互联网公司都在使用 Python&a…

java数据结构与算法刷题-----LeetCode215. 数组中的第K个最大元素

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 文章目录 解题思路&#xff1a;时间复杂度O( n n n)&#xff0c;空间复杂度…

SQL Server 2008R2 日志文件大小设置及查询

SQL Server 2008R2 建立数据库存在日志无限增长问题&#xff0c;造成磁盘内存不足。本文解决这个问题&#xff0c;如下&#xff1a; 1.设置日志文件的最大大小 USE master; GO ALTER DATABASE [D_total] MODIFY FILE (NAME D_total_log, -- 日志文件的逻辑名称MAXSIZE 200…