Leetcode 977. 有序数组的平方 Squares of a sorted array -双指针法 - Python

Leetcode 977. 有序数组的平方 Squares of a sorted array -双指针法 - Python

本篇文章为笔者的LeetCode刷题笔记。文章整体分为两部分：

1.笔者自己思考的算法及代码。

2.LeetCode官方给出的最优算法及代码。通过对比这两部分算法和代码的异同，笔者的算法思想和编程水平有了显著地提升。如果这篇文章能帮到你那真是再好不过了！

一、笔者思考的算法

A.算法
双指针法
由于有序数组的元素平方后最大值肯定是出现在数组左右两侧（有正负数的情况）；右侧（只有正数或左边负数的绝对值小于右侧正数的绝对值）；左侧（同上，方向互换）

那么只需要两个指针front，rear。一个在前一个在后，分别比较数组两侧元素的平方大小，择其大者从最右侧插入新建数组（大者在右）。front和rear指针逐渐向中间夹逼，遍历整个数组。

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        front, rear, rearResult = 0, n-1, n-1
        result = [0]*n        #新建与nums相同大小数组
        while front <= rear:    #当front > rear时， 遍历结束
            if nums[front]**2 <= nums[rear]**2:     #比较rear，front指针所指元素平方大小
                result[rearResult] = nums[rear]**2
                rear -= 1        #rear左移1位
            else:
                result[rearResult] = nums[front]**2
                front += 1        #front右移1位
            rearResult -= 1        #rearResult在每次插入到新数组后左移1位
        return result

B.复杂度分析

时间复杂度：O(N) 只需遍历整个数组即可。

空间复杂度: O(N) 用到了额外数组result。

二.官方算法

官方算法与我的算法几乎一致

三.笔者小结

1.此题关键点在于，给定数组的平方值大小是呈形似Y=x^2图像分布的。

2.于是联想到运用双指针法，从数组两侧夹逼比较数组元素大小，择其大者存入新建数组。

3.注意while循环结束条件为front > rear。