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

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

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。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710668.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存