有序数组的平方

Leetcode Link: 977. 有序数组的平方 - 力扣（LeetCode）

题目

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

解法一

思路： 按照题意来即可，直接把结果排序

题解：时间 $O(N+NlogN)$

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        new = [val**2 for val in nums]
        new.sort()
        return new

解法二

思路：双指针 由于已经排好序了，因此我们可以直接使用对向双指针来比较绝对值大小，答案数组的最大值一定是在原数组的两边的，这样不断缩减，完成此项任务。

题解：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        pre = 0
        tail = len(nums)-1
        new = []
        while(pre <= tail):
            if abs(nums[pre]) > abs(nums[tail]):
                new.append(nums[pre]**2)
                pre += 1
            else:
                new.append(nums[tail]**2)
                tail -= 1
        return new[::-1]

Note

如果 new 是列表，需要最后逆序一下 实际上也可以使用collections.deque()来完成，添加元素的时候直接appendleft就可以避免最后的逆序了

另一种不逆序的

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l = 0
        r = len(nums) - 1
        res = [0] * len(nums)
        p = len(nums)-1
        while(l<=r):
            if abs(nums[l]) < abs(nums[r]):
                res[p] = nums[r] ** 2
                r -= 1
            else:
                res[p] = nums[l] ** 2
                l += 1
            p -= 1
        return res
 

启发和联系