当前位置:网站首页>leetcode--977. Squares of a Sorted Array
leetcode--977. Squares of a Sorted Array
2022-04-23 14:03:00 【Amelia who loves learning】
-
Problem:Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order. 1
-
Example :
# Example 1
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
# Example 2
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
- Tips :
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.
- Ideas :
First, sort each value in the list
Output with built-in sorting algorithm
- Solution 1 – direct :
class Solution:
def sortedSquares(self, nums):
dou_nums = [x * x for x in nums]
return sorted(dou_nums)
- Ideas :
Set an empty list to store qualified values , Set the head and tail pointer to head and tail
When the head pointer is not equal to the tail pointer , Continue operation , If the square of the head is greater than the square of the tail , Insert the header value into the list and add one to the pointer ; If the square of the tail value is greater than or equal to the square of the head value , Insert the square of the tail value into the list and add one to the tail pointer ; If the head pointer is greater than or equal to the tail pointer , And then jump out of the loop
Insert the remaining header values squared into the list
Returns the reverse order of the list
- Solution 2 – Double pointer :
class Solution:
def sortedSquares(self, nums):
dou_nums = []
a, b = 0, len(nums)-1
while a != b:
dou_a = nums[a] ** 2
dou_b = nums[b] ** 2
if dou_a > dou_b:
dou_nums.append(dou_a)
a += 1
elif dou_b >= dou_a:
dou_nums.append(dou_b)
b -= 1
if a >= b:
break
dou_nums.append(nums[a]**2)
return dou_nums[::-1]
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/squares-of-a-sorted-array ︎
版权声明
本文为[Amelia who loves learning]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231341317276.html
边栏推荐
猜你喜欢
Autumn recruitment in 2021, salary ranking No
Crontab timing task output generates a large number of mail and runs out of file system inode problem processing
Wechat applet
mysql新表,自增id长达20位,原因竟是......
基于Ocelot的gRpc网关
基於CM管理的CDH集群集成Phoenix
PySide2
Oracle告警日志alert.log和跟踪trace文件中文乱码显示
The latest development of fed digital currency
微信小程序通过低功耗蓝牙设备进行定位及测距(二)
随机推荐
linux安装mysql后修改密码
专题测试05·二重积分【李艳芳全程班】
趣谈网络协议
可否把模板的头文件和源文件分开编译
微信小程序 input隐藏和不可操作的设置
smart-doc + torna生成接口文档
Jenkins construction and use
Basic knowledge learning record
Crontab timing task output generates a large number of mail and runs out of file system inode problem processing
Elmo (bilstm-crf + Elmo) (conll-2003 named entity recognition NER)
Wechat applet
go 语言 数组,字符串,切片
Nodejs安装及环境配置
第十五章 软件工程新技术
基础知识学习记录
FBS(fman build system)打包
Expression「Func「TSource, object」」 转Expression「Func「TSource, object」」[]
容差分析相关的计算公式
YARN线上动态资源调优
关于stream流,浅记一下------