Squares of a Sorted Array

Q: Quelle est la complexité temporelle de « Squares of a Sorted Array » ?

La solution à deux pointeurs s’exécute en temps O(n) : chaque valeur est mise au carré et placée une seule fois. La mise au carré, puis le tri, coûte O(n log n) . Les deux utilisent O(n) de mémoire pour le résultat.

FacileDeux pointeurs Tri

+10

Vous disposez d’un tableau d’entiers nums trié par ordre non décroissant. Il peut contenir des valeurs négatives. Élevez chaque valeur au carré et renvoyez les carrés dans un nouveau tableau, lui aussi trié par ordre non décroissant.

Fonction

sortedSquares(nums: integer-array) → integer-array

numsinteger-array: le tableau trié d’entiers, les nombres négatifs sont autorisés
Renvoieinteger-array: le carré de chaque valeur, trié par ordre non décroissant

Contraintes

1 ≤ nums.length ≤ 4000
-10⁴ ≤ nums[i] ≤ 10⁴
nums est trié par ordre non décroissant.

Exemples

Entrée: nums = [-6, -2, 1, 3, 7]
Sortie: [1, 4, 9, 36, 49]
Explication: Les carrés dans l’ordre d’origine sont 36, 4, 1, 9 et 49. Les valeurs négatives -6 et -2 donnent de grands carrés, donc le tri déplace 36 près de la fin : [1, 4, 9, 36, 49].

Entrée: nums = [-9, -4, -1]
Sortie: [1, 16, 81]
Explication: Chaque valeur est négative, donc les carrés apparaissent dans l’ordre inverse : 81, 16, 1 devient [1, 16, 81].

+14 tests cachés à la soumission

Pour aller plus loin

Mettre au carré et trier prend O(n log n). Peux-tu le faire en O(n) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le fait d’élever au carré conserve l’ordre des valeurs non négatives, mais inverse celui des valeurs négatives ; les carrés ne sont donc pas triés. Les trier à nouveau fonctionne, mais ignore l’ordre initial. Le point essentiel : le plus grand carré provient toujours de l’une des deux extrémités de nums. Compare les deux extrémités, place le carré le plus grand à la fin du résultat et avance vers le centre.

Carré, puis trier

Intuition

Créez un nouveau tableau avec le carré de chaque valeur, puis triez-le. Les carrés ne sont jamais négatifs, et le tri les met dans l’ordre, quelle que soit leur provenance.

Pour [-6, -2, 1, 3, 7], les carrés sont [36, 4, 1, 9, 49], et le tri donne [1, 4, 9, 36, 49].

Le tri coûte O(n log n). C’est suffisamment rapide ici, mais il traite l’entrée comme si elle n’avait aucun ordre. L’approche suivante exploite l’ordre et ne nécessite qu’un seul parcours.

Algorithme

Crée un tableau avec x * x pour chaque x dans nums.
Trie-le par ordre numérique croissant.
Renvoie-le.

def sortedSquares(nums):
    return sorted(x * x for x in nums)

Deux pointeurs partant des deux extrémités

Intuition

Considérez les carrés comme la distance à 0, élevée au carré. Dans un tableau trié, les valeurs les plus éloignées de 0 se trouvent aux deux extrémités : la valeur la plus négative à gauche et la plus positive à droite. Le plus grand carré est donc nums[left]² ou nums[right]², jamais celui d’une valeur intermédiaire.

Gardez left à 0 et right à n-1, puis remplissez le résultat en partant de sa dernière position et en remontant. À chaque étape, comparez les carrés des deux extrémités, écrivez le plus grand à la position courante et déplacez le pointeur correspondant vers l’intérieur. Les valeurs situées entre les pointeurs forment à nouveau un tableau trié ; le même principe s’applique donc à chaque étape.

Pour [-6, -2, 1, 3, 7] : 49 l’emporte sur 36 et va à la dernière position. Puis 36 l’emporte sur 9, 9 l’emporte sur 4, 4 l’emporte sur 1, et le 1 remplit la position 0. Le résultat est [1, 4, 9, 36, 49]. Chaque valeur est placée une seule fois : complexité temporelle O(n), et le résultat est le seul tableau supplémentaire.

Algorithme

Créez un tableau de résultats de longueur n. Définissez left sur 0 et right sur n-1.
Parcourez les positions avec pos, de n-1 à 0.
Comparez nums[left]² à nums[right]².
Écrivez le carré le plus grand à la position pos et déplacez ce pointeur d’un pas vers l’intérieur.
Retournez le résultat.

def sortedSquares(nums):
    n = len(nums)
    result = [0] * n
    left, right = 0, n - 1
    # the largest square left is always at one of the two ends
    for pos in range(n - 1, -1, -1):
        left_sq = nums[left] * nums[left]
        right_sq = nums[right] * nums[right]
        if left_sq > right_sq:
            result[pos] = left_sq
            left += 1
        else:
            result[pos] = right_sq
            right -= 1
    return result

Pièges et cas limites

La version à deux pointeurs est courte, mais quelques détails peuvent la compromettre.

Remplir le résultat depuis le début. Le plus petit carré se trouve là où les valeurs traversent 0, ce qui peut être n’importe où au milieu. Les extrémités indiquent uniquement le plus grand carré. Remplissez depuis la fin.
Comparer nums[left] et nums[right] au lieu de comparer leurs carrés ou leurs valeurs absolues. -6 est inférieur à 3, mais son carré est supérieur.
S’arrêter lorsque left rejoint right. Lorsqu’ils sont égaux, une valeur n’a pas encore été placée ; parcourez chaque position du résultat ou utilisez left <= right.
Une entrée entièrement négative ou entièrement positive. Avec [-9, -4, -1], le pointeur gauche fait tout le travail, et avec [2, 5, 8], c’est le pointeur droit. Les deux cas doivent tout de même produire un résultat trié.
En JavaScript et TypeScript, sort() sans comparateur trie les nombres comme du texte : [1, 4, 36, 9] devient donc [1, 36, 4, 9]. Passez (a, b) => a - b.

Questions fréquentes4

Quelle est la complexité temporelle de « Squares of a Sorted Array » ?

La solution à deux pointeurs s’exécute en temps O(n) : chaque valeur est mise au carré et placée une seule fois. La mise au carré, puis le tri, coûte O(n log n). Les deux utilisent O(n) de mémoire pour le résultat.

Pourquoi le plus grand carré provient-il de l'une des deux extrémités ?

Un carré augmente avec la distance par rapport à 0. Dans un tableau trié, la valeur la plus éloignée de 0 en dessous de 0 est la première, et la valeur la plus éloignée de 0 au-dessus de 0 est la dernière. Chaque valeur située entre les deux est plus proche de 0 que l’une d’elles, donc son carré ne peut pas être le plus grand.

Peux-tu plutôt remplir le résultat en partant du début ?

Oui, mais tu dois d’abord trouver où les valeurs passent par 0, par exemple à l’aide d’une recherche binaire. Ensuite, deux pointeurs avancent vers l’extérieur à partir de ce point, comme lors de la fusion de deux listes triées : les valeurs négatives se lisent de droite à gauche et les valeurs non négatives de gauche à droite. Remplir à partir de la fin évite la recherche, car les extrémités sont connues dès le départ.

Squares of a Sorted Array est-il un problème de fusion ?

Déguisées, oui. Les valeurs négatives au carré forment une liste triée (à lire de droite à gauche), et les valeurs non négatives au carré en forment une autre. Les combiner correspond à l’étape de fusion du tri fusion, ce qui explique pourquoi cela tient en un seul parcours linéaire.

Python

def sortedSquares(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

nums = [-6, -2, 1, 3, 7]

Attendu

[1, 4, 9, 36, 49]