LeetCode977（有序数组的平方）

武师叔

发布于 2022-09-26 17:28:03

2820

发布于 2022-09-26 17:28:03

文章被收录于专栏：师叔的搬砖之路师叔的搬砖之路

每日一题——LeetCode977（有序数组的平方）

https://www.bilibili.com/video/BV17S4y1m7d1

题意

难度：简单

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

方法一：直接排序

思路与算法

元组中数平方后直接排序，因为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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法