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

题意

难度：简单

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

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

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

方法一：直接排序

思路与算法

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

代码

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

点击并拖拽以移动

方法二：双指针

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

图解如下：

img点击并拖拽以移动

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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