Leetcode 977. Squares of a Sorted Array

Tyan

发布于 2021-08-20 12:13:42

3260

发布于 2021-08-20 12:13:42

文章被收录于专栏：SnailTyan

1. Description

2. Solution

**解析：**Version 1，采用双指针，先计算平方和，再比较大小，较大的更新到结果数组中。Version 2先比较二者绝对值大小，再将平方更新到结果中。

Version 1

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i = 0
        j = n - 1
        result = [0] * n
        index = n - 1
        x = nums[i] ** 2
        y = nums[j] ** 2
        while i <= j:    
            if x <= y:
                result[index] = y
                index -= 1
                j -= 1
                y = nums[j] ** 2
            else:
                result[index] = x
                index -= 1
                i += 1
                x = nums[i] ** 2
        return result

Version 2

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i = 0
        j = n - 1
        result = [0] * n
        index = n - 1
        while i <= j: 
            x = nums[i]
            y = nums[j]
            if abs(x) <= abs(y):
                result[index] = y * y
                index -= 1
                j -= 1
                y = nums[j]
            else:
                result[index] = x * x
                index -= 1
                i += 1
                x = nums[i]
        return result