LeetCode ＃977.有序数组的平方

力扣 | 977.有序数组的平方

题目截图

方法一：直接排序

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)

测试用全部代码

from typing import List

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        return sorted(num * num for num in nums)
    
class main:
    a = Solution()
    nums = [-5,-3,-2,-1]
    b = a.sortedSquares(nums)

    print(b)

if __name__ == '__main__':
    main()

sorted() 函数

Python sorted() 函数 | 菜鸟教程

方法二：双指针

题目所给为非递减顺序排序，平方后可能产生顺序变化只需看原数组元素是否为零。

利用如下代码记录负数所在下标。

        for i in range(0, n):
            if nums[i]<0:
                flag = i
            else:
                break

 也可以利用 enumerate()函数

Python enumerate() 函数 | 菜鸟教程

for i, num in enumerate(nums):
            if num < 0:
                flag = i
            else:
                break

拓展：自己实现enumerate()函数

def my_enumerate(obj):
    for i in range(len(obj)):
        yield i,obj[i]

 分别设置左右指针left=flag，right=flag+1，左指针指向第一个负数，向左移动。右指针指向第一个非负数，向右移动。

设置循环，只要左右指针没有都到达最左和最右边，就一直循环。

优先考虑两种极端情况，即，做指针在最左边，但是右指针没有到达最右边；以及右指针在最右边，但是左指针没有到达最左边。

1.当左指针在最左时，一直添加右指针指向的元素，并不断右移右指针。

2.反过来同2理。

3.当左指针指向元素小于等于右指针指向元素：添加左边的元素，并将左指针左移。

4.反过来同3理。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        flag = 0
        for i in range(0, n):
            if nums[i]<0:
                flag = i
            else:
                break
        left, right = flag, flag+1
        ans = []
        while left >= 0 or right < n:
            if left < 0:
                ans.append(nums[right] * nums[right])
                right += 1
            elif right == n:
                ans.append(nums[left] * nums[left])
                left -= 1
            elif (nums[left]*nums[left]) <= (nums[right] * nums[right]):
                ans.append(nums[left] * nums[left])
                left -= 1
            else:
                ans.append(nums[right] * nums[right])
                right += 1
        return ans

方法三：双指针

将两个指针一开始就放在左右两边，比较指针指向元素平方的大小后排入数组，让他们往中间移动。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right, pos= 0, n-1, n-1
        ans = [0]* n
        while left <= right :
            if nums[left] * nums[left] > nums[right] * nums[right]:
                ans[pos] = (nums[left] * nums[left])
                left += 1
            else:
                ans[pos] = (nums[right] * nums[right])
                right -=1
            pos -= 1
        return ans