[leetcode] 977 - carré du tableau ordonné

Pour vous donner un coup de pouce Ordre non décroissant Tableau entier trié nums,Retour Au carré de chaque nombre Nouveau tableau composé,Les exigences sont également conformes à Ordre non décroissant Trier.

Exemple 1：

Entrée： nums = [-4,-1,0,3,10]
Produits： [0,1,9,16,100]
Explication： Au carré,Le tableau devient [16,1,0,9,100]
Après tri,Le tableau devient [0,1,9,16,100]

Exemple 2：

Entrée： nums = [-7,-3,2,3,11]
Produits： [4,9,9,49,121]

Conseils：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums Appuyez sur Ordre non décroissant Trier

Niveau avancé：

S'il vous plaît concevoir la complexité du temps pour O(n) Algorithme pour résoudre ce problème

#Tri direct
class Solution(object):
    def sortedSquares(self, nums):
        return sorted(num*num for num in nums)
#Complexité temporelle：O(n \log n)O(nlogn)
#Complexité spatiale：O(\log n)O(logn)

#Double pointeur
#Parce que la séquence du tableau est ascendante,Les carrés sont tous des nombres positifs,Donc commencez par les deux extrémités,Les nombres dont la valeur absolue est grande sont d'abord carrés dans la séquence
class Solution(object):
    def sortedSquares(self, nums):
        a = 0
        b = len(nums)-1
        result = []
        while a<=b:
            if abs(nums[a])>=abs(nums[b]):
                result.append(nums[a]*nums[a])
                a+=1
            else:
                result.append(nums[b]*nums[b])
                b-=1
        return result[::-1]