LeetCode 刷题 977- 简单 - 有序数组的平方

ベ布小禅

关注

发布于: 2 小时前

前言

算法作为极其重要的一点，是大学生毕业找工作的核心竞争力，所以为了不落后与人，开始刷力扣算法题！

第一遍，不求最优解，但求能过！！！

📢 这是我刷第 9/100 道力扣简单题

一、题目描述

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

提示：

1 <= nums.length <= 104-104 <= nums[i] <= 104nums 已按非递减顺序排序

进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题

二、实例

示例 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]

复制代码

三、解题思路

使用内置函数法
遍历，平方，比较，排序
排序可以使用内置函数 sqrt()
双指针法
因为原来的数组/列表是有序的，只不过需要平方，然后再排序，所以可以使用双指针法
类似于二分查找那种方法
我们需要两个数分别来记录数组/列表左边和右边
然后比较左边和右边的大小，将大的添加进一个数组/列表
最后这个数组/列表就是我们的答案

三、代码

内置函数法
时间复杂度：O(n)
空间复杂度：O(1)

   from typing import List      class Solution:       def sortedSquares(self, nums: List[int]) -> List[int]:           ans = []           for i in nums:               ans.append(i**2)           return sorted(ans)

复制代码

双指针法
时间复杂度：O(n)
空间复杂度：O(1)

   class Solution:       def sortedSquares(self, nums: List[int]) -> List[int]:           ans = []           n = len(nums)           m = 0           while m <= n-1:               i = nums[m]*nums[m]               j = nums[n-1]*nums[n-1]               if i >= j:                   ans.append(i)                   m += 1               else:                   ans.append(j)                   n -= 1           return ans[::-1]

复制代码

结语

坚持最重要，每日一题必不可少！

发布于: 2 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/46de8d0506f69fdc543babacb】。文章转载请联系作者。

ベ布小禅

关注

还未添加个人签名 2021.04.06 加入

平平无奇一萌新，默默无闻学IT，我是布小禅，一个网络专业却对编程及其感兴趣的小白！目前在学python和Java，都很浅显，平时爱写点学习笔记。IT技术交流群：1039347613 也可以联系本人企鹅：2228660752 v：Smly0413

发布

暂无评论

创作场景

LeetCode 刷题 977- 简单 - 有序数组的平方

前言

一、题目描述

二、实例

三、解题思路

三、代码

结语

ベ布小禅

评论