每日一题 | LeetCode977 有序数组的平方

作者：武师叔

2022 年 6 月 07 日
本文字数：682 字
阅读完需：约 2 分钟

题意

难度：简单

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

示例

输入：nums = [-4,-1,0,3,10]输出：[0,1,9,16,100]

解释：平方后，数组变为 [16,1,0,9,100]排序后，数组变为 [0,1,9,16,100]

输入：nums = [-7,-3,2,3,11]输出：[4,9,9,49,121]

思路与算法

方法一：直接排序

元组中数平方后直接排序，因为 python 中有 sorted()函数直接排序。所以 python 学得好，代码打得少！

代码

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:return sorted(num * num for num in nums)

复制代码

方法二：双指针

通过题目件其实我们可以得出，平方以后的最大值肯定出现在两侧，不是左边就是右边（负数的平方为正数）。首先初始化 left 和 right 指针，新建 res 数组，site 指针指向 res 数组的尾部。

图解如下：

代码实现：

 class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:    if len(nums) == 1:        return [nums[0] * nums[0]]
    # 初始化双指针    left = 0    right = len(nums) - 1
    # 存储结果数组，从数组末尾开始存储    res = [-1] * len(nums)    site = len(nums) - 1
    # 注意这里是 <=    while left <= right:        # 从两端遍历，将平方数组大得存储在 res 数组中        if nums[left] * nums[left] < nums[right] * nums[right]:            res[site] = nums[right] * nums[right]            right -= 1        else:            res[site] = nums[left] * nums[left]            left += 1
        site -= 1
    return res

复制代码

发布于: 刚刚阅读数: 5

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

武师叔

关注

每天丰富自己，去过自己想要的生活！ 2022.04.28 加入

一个喜欢最新技术，研发的人工智能专业的大二学生，用自己的代码做一些有意义的事情！目前大二结束有去大厂研发岗实习的计划，每天丰富自己的技术，去过自己想要的实习生活。

发布

暂无评论

创作场景

每日一题 | LeetCode977 有序数组的平方

题意​

示例

思路与算法

方法一：直接排序

方法二：双指针

武师叔

评论

题意