Squares of a Sorted Array
Ricevi un array di numeri interi nums ordinato in ordine non decrescente. Può contenere valori negativi. Eleva al quadrato ogni valore e restituisci i quadrati in un nuovo array, anch’esso ordinato in ordine non decrescente.
Funzione
- numsinteger-array
- l'array ordinato di numeri interi, sono ammessi i numeri negativi
- Restituisceinteger-array
- il quadrato di ogni valore, ordinato in ordine non decrescente
Vincoli
1 ≤ nums.length ≤ 4000-104 ≤ nums[i] ≤ 104numsè ordinato in ordine non decrescente.
Esempi
- Input
- nums = [-6, -2, 1, 3, 7]
- Output
- [1, 4, 9, 36, 49]
- Spiegazione
- I quadrati nell'ordine originale sono 36, 4, 1, 9 e 49. I valori negativi -6 e -2 danno quadrati grandi, quindi l'ordinamento sposta 36 verso la fine:
[1, 4, 9, 36, 49].
- Input
- nums = [-9, -4, -1]
- Output
- [1, 16, 81]
- Spiegazione
- Ogni valore è negativo, quindi i quadrati escono in ordine inverso: 81, 16, 1 diventa
[1, 16, 81].
+14 test nascosti all’invio
Per approfondire
Elevare al quadrato e ordinare richiede O(n log n). Riesci a farlo in O(n)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Eleva al quadrato
[-6, -2, 1, 3, 7]a mano. Quale parte dell'array perde il suo ordine e perché?Il quadrato più grande deriva sempre dal primo o dall’ultimo valore di
nums, perché questi due sono i più lontani da 0.Metti un puntatore a ciascuna estremità. Confronta i due quadrati, scrivi quello più grande in fondo al risultato e sposta quel puntatore verso l’interno. Ripeti finché ogni posizione non è occupata.
Soluzione
Elevare al quadrato mantiene l’ordine dei valori non negativi ma inverte quello dei valori negativi, quindi i quadrati non sono ordinati. Ordinarli di nuovo funziona, ma ignora l’ordine in cui ti sono stati forniti. Il fatto fondamentale: il quadrato più grande proviene sempre da una delle due estremità di nums. Confronta le due estremità, inserisci il quadrato più grande in fondo al risultato e procedi verso l’interno.
Eleva al quadrato, poi ordina
Intuizione
Crea un nuovo array con il quadrato di ogni valore, poi ordinalo. I quadrati non sono mai negativi e l’ordinamento li mette in ordine indipendentemente dalla loro posizione iniziale.
Per [-6, -2, 1, 3, 7] i quadrati sono [36, 4, 1, 9, 49], e l’ordinamento dà [1, 4, 9, 36, 49].
L’ordinamento ha un costo di O(n log n). Qui è abbastanza veloce, ma tratta l’input come se non avesse alcun ordine. L’approccio successivo sfrutta l’ordine e richiede un solo passaggio.
Algoritmo
- Crea un array con
x * xper ognixinnums. - Ordinalo in ordine numerico crescente.
- Restituiscilo.
def sortedSquares(nums):
return sorted(x * x for x in nums)Due puntatori da entrambe le estremità
Intuizione
Considera i quadrati come le distanze da 0, elevate al quadrato. In un array ordinato, i valori più lontani da 0 si trovano alle due estremità: il valore più negativo a sinistra e quello più positivo a destra. Quindi il quadrato più grande è nums[left]² oppure nums[right]², mai uno qualsiasi tra questi.
Mantieni left a 0 e right a n-1, e riempi il risultato partendo dall'ultima posizione e procedendo all'indietro. A ogni passaggio, confronta i quadrati alle due estremità, scrivi quello più grande nella posizione corrente e sposta verso l'interno il puntatore corrispondente. Ciò che rimane tra i puntatori è ancora un array ordinato, quindi lo stesso principio vale a ogni passaggio.
Con [-6, -2, 1, 3, 7]: 49 supera 36 e va all'ultima posizione. Poi 36 supera 9, 9 supera 4, 4 supera 1 e l'1 riempie la posizione 0. Il risultato è [1, 4, 9, 36, 49]. Ogni valore viene posizionato una volta: tempo O(n) e il risultato è l'unico array aggiuntivo.
Algoritmo
- Crea un array risultato di lunghezza
n. Impostaleftsu 0 erightsun-1. - Scorri la posizione
posdan-1fino a 0. - Confronta
nums[left]²connums[right]². - Scrivi il quadrato più grande in
pose sposta quel puntatore di un passo verso l'interno. - Restituisci il risultato.
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
Trappole e casi limite
La versione con due puntatori è breve, ma alcuni dettagli possono comprometterla.
- Riempire il risultato dall'inizio. Il quadrato più piccolo si trova dove i valori attraversano lo 0, che può essere in qualsiasi punto centrale. Le estremità indicano solo il quadrato più grande. Riempi il risultato dalla fine.
- Confrontare
nums[left]connums[right]invece dei loro quadrati o valori assoluti. -6 è minore di 3, ma il suo quadrato è maggiore. - Fermarsi quando
leftraggiungeright. Quando sono uguali, c'è ancora un valore da posizionare; scorri tutte le posizioni del risultato oppure usaleft <= right. - Input tutti negativi o tutti positivi. Con
[-9, -4, -1]il puntatore sinistro fa tutto il lavoro, mentre con[2, 5, 8]lo fa quello destro. Entrambi devono comunque produrre un risultato ordinato. - In JavaScript e TypeScript,
sort()senza un comparatore ordina i numeri come testo, quindi[1, 4, 36, 9]diventa[1, 36, 4, 9]. Passa(a, b) => a - b.
Domande frequenti4
Qual è la complessità temporale di Squares of a Sorted Array?
La soluzione con due puntatori richiede O(n) tempo: ogni valore viene elevato al quadrato e inserito una sola volta. Elevare al quadrato e poi ordinare richiede O(n log n). Entrambe usano O(n) memoria per il risultato.
Perché il quadrato più grande proviene da una delle due estremità?
Un quadrato cresce con la distanza da 0. In un array ordinato, il valore più lontano da 0 tra quelli inferiori a 0 è il primo, e il valore più lontano da 0 tra quelli superiori a 0 è l'ultimo. Ogni valore intermedio è più vicino a 0 di uno dei due, quindi il suo quadrato non può essere il più grande.
Puoi inserire il risultato dall'inizio invece?
Sì, ma prima devi trovare il punto in cui i valori attraversano 0, ad esempio con una ricerca binaria. Poi due puntatori si spostano verso l’esterno a partire da quel punto, come nell’unione di due liste ordinate: i valori negativi si leggono da destra a sinistra e quelli non negativi da sinistra a destra. Riempire partendo dal fondo evita la ricerca, perché gli estremi sono noti fin dall’inizio.
Squares of a Sorted Array è un problema di merge?
Sotto mentite spoglie, sì. I valori negativi elevati al quadrato formano una lista ordinata (da leggere da destra a sinistra), e i valori non negativi elevati al quadrato ne formano un’altra. Combinarle è il passaggio di fusione del merge sort, ed è per questo che basta un’unica scansione lineare.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def sortedSquares(nums):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums = [-6, -2, 1, 3, 7]
Atteso
[1, 4, 9, 36, 49]