【Leetcode刷题Python】977. 有序数组的平方

1 题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

2 解析

（1）方法一：使用python内置的sort的快排 空间复杂度O(n)，时间复杂度O(nlogn) （2）方法二 直接插入排序，但是超过时间限制 时间复杂度 O ( n 2 ) O(n^2) O(n2)，时间复杂度O(1) （3）方法三 双指针 时间复杂度O(n)，空间复杂度O(n)

3 python 实现

（1）方法一

# 快速排序
def sortedSquares(self, nums: List[int]) -> List[int]:
    res = []
    for i in nums:
       res.append(i*i)
    # 第一种方法，使用python内置的sort方法
    res.sort()
    # 第二种方法，自己写快排算法
    self.QuckSort(res,0,len(nums)-1)
    return res 
    
def partition(self,arr,low,high):
    i = low-1
    pivot =arr[high]
    for j in range(low,high):
        if arr[j]=0 and temp List[int]:
    if len(nums)==1:
        return [nums[0]*nums[0]]
    res = [-1]*len(nums)
    idx = len(nums)-1
    right =len(nums)-1
    left = 0
    while leftnums[right]*nums[right]:
            res[idx] = nums[left]*nums[left]
            left +=1
        else:
            res[idx] = nums[right]*nums[right]
            right -=1     
        idx -=1
    return res