Leetcode 977. Squares of a Sorted Array

冷不防 2022-09-05 14:51 37阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Squares of a Sorted Array][]

## 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

## Reference ##

1.  [https://leetcode.com/problems/squares-of-a-sorted-array/][https_leetcode.com_problems_squares-of-a-sorted-array]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Squares of a Sorted Array]: /images/20220829/624fe06e760d4690a3e507fb79eb14d0.png
[https_leetcode.com_problems_squares-of-a-sorted-array]: https://leetcode.com/problems/squares-of-a-sorted-array/