Basi degli array e operazioni in-place
Ripassi l'indicizzazione e la mutazione e analizzi le insidie più comuni degli array nei colloqui, come gli errori off-by-one e la modifica di una lista durante l'iterazione
Basi degli array e operazioni in-place è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Gli array come memoria contigua
Sotto il cofano, una lista Python è supportata da un array dinamico: un blocco contiguo di memoria in cui gli elementi sono memorizzati a indirizzi consecutivi. Questa disposizione consente l'accesso casuale O(1) tramite indice: Python calcola istantaneamente address = base + index × element_size. Gli inserimenti o le eliminazioni nel mezzo richiedono lo spostamento di tutti gli elementi successivi, con un costo O(n). Questa asimmetria è all'origine della maggior parte dei compromessi sugli array discussi nei colloqui.
nums = [10, 20, 30, 40, 50]
# O(1) random access
print(nums[2]) # 30
print(nums[-1]) # 50
# O(1) append (amortised)
nums.append(60)
print(nums) # [10,20,30,40,50,60]
# O(n) insert at beginning
nums.insert(0, 0) # shifts all elements right
print(nums) # [0,10,20,30,40,50,60]Errore off-by-one: il classico bug degli array
Gli errori off-by-one sono la causa più frequente delle risposte errate nei problemi sugli array. L'indicizzazione a partire da 0 di Python significa che l'ultimo indice valido è len(arr) - 1. Quando scrive i cicli, stabilisca se serve < o <= verificando la condizione al limite con l'input valido più piccolo (n=1 o n=2). Prima di inviare la soluzione, verifichi sempre il limite usando esempi concreti.
def find_max(nums):
# Use len(nums)-1 as last index
max_val = nums[0] # safe if n >= 1
for i in range(1, len(nums)): # start at 1, not 0
if nums[i] > max_val:
max_val = nums[i]
return max_val
print(find_max([3, 1, 4, 1, 5])) # 5
print(find_max([7])) # 7 (single element)
# Would crash if we accessed nums[len(nums)]Inversione in-place con due puntatori
Per invertire un array in-place si usano due puntatori che partono dalle estremità opposte e si scambiano gli elementi procedendo verso il centro, finché si incontrano. Servono O(1) di spazio aggiuntivo e O(n) di tempo. La condizione left < right (strettamente minore) garantisce la correttezza sia per le lunghezze pari sia per quelle dispari: con un numero dispari di elementi, quello centrale rimane automaticamente al suo posto.
def reverse_inplace(arr):
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
# Space: O(1) Time: O(n)
a = [1, 2, 3, 4, 5]
reverse_inplace(a)
print(a) # [5, 4, 3, 2, 1]
b = [1, 2, 3]
reverse_inplace(b)
print(b) # [3, 2, 1] middle element unchangedRuotare un array in-place
È possibile ruotare un array verso destra di k posizioni in-place invertendo tre segmenti: prima si inverte l'intero array, poi i primi k elementi e infine i restanti n-k elementi. Si ottengono O(n) di tempo e O(1) di spazio, molto meglio dell'approccio con slicing e concatenazione, che richiede O(n) di spazio. Riduca sempre k modulo n per gestire k ≥ n.
def rotate(nums, k):
n = len(nums)
k %= n # handle k >= n
def rev(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1; r -= 1
rev(0, n-1) # reverse all
rev(0, k-1) # reverse first k
rev(k, n-1) # reverse rest
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
print(a) # [5, 6, 7, 1, 2, 3, 4]Rimuovere elementi in-place
La rimozione di duplicati o di valori target in-place usa un puntatore di scrittura che indica dove scrivere il prossimo elemento valido. Il puntatore di lettura scorre in avanti; quando trova un elemento valido, lo copia nella posizione di scrittura e fa avanzare entrambi i puntatori. Questo è il modello fondamentale per problemi di LeetCode come 'remove element', 'remove duplicates from sorted array' e 'move zeroes'.
def remove_element(nums, val):
write = 0
for read in range(len(nums)):
if nums[read] != val:
nums[write] = nums[read]
write += 1
return write # new length
nums = [3, 2, 2, 3]
new_len = remove_element(nums, 3)
print(nums[:new_len]) # [2, 2]
nums2 = [0, 1, 2, 2, 3, 0, 4, 2]
new_len2 = remove_element(nums2, 2)
print(nums2[:new_len2]) # [0, 1, 3, 0, 4]Spostare gli zeri: puntatore di lettura-scrittura
Spostare tutti gli zeri alla fine di un array mantenendo l'ordine degli elementi diversi da zero. L'approccio con puntatore di lettura-scrittura colloca ogni elemento diverso da zero nella posizione di scrittura, quindi riempie la parte finale con gli zeri. Un approccio alternativo sposta gli zeri all'indietro tramite scambi, preservando l'ordine senza una seconda fase di riempimento. Entrambi richiedono tempo O(n) e spazio O(1).
def move_zeroes(nums):
write = 0
# Move all non-zeroes to front
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# Fill rest with zeroes
while write < len(nums):
nums[write] = 0
write += 1
a = [0, 1, 0, 3, 12]
move_zeroes(a)
print(a) # [1, 3, 12, 0, 0]Elevare al quadrato e ordinare sul posto
Dato un array ordinato di interi (eventualmente negativi), restituire un array contenente i loro quadrati in ordine crescente. L'approccio ingenuo eleva prima al quadrato e poi ordina: O(n log n). L'approccio ottimale con due puntatori sfrutta il fatto che i quadrati più grandi provengono da una delle due estremità dell'input ordinato: confronta i valori assoluti degli elementi più a sinistra e più a destra e riempie il risultato da destra verso sinistra in tempo O(n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1 # fill from the right
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Trovare il pivot e partizionare
Il problema della bandiera nazionale olandese partiziona un array sul posto in tre sezioni (minori del pivot, uguali al pivot, maggiori del pivot) usando tre puntatori. Questo è il passaggio fondamentale di quick sort e la soluzione al problema di LeetCode 'sort colors'. Mantenere l'invariante secondo cui gli elementi prima del puntatore low sono < pivot e quelli dopo il puntatore high sono > pivot guida l'algoritmo.
def sort_colors(nums):
# Dutch national flag: 0s, 1s, 2s
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # don't advance mid: new nums[mid] unexamined
a = [2, 0, 2, 1, 1, 0]
sort_colors(a)
print(a) # [0, 0, 1, 1, 2, 2]Modificare gli elementi di un array durante l'iterazione
È possibile modificare i valori degli elementi (ad esempio, moltiplicandoli per -1 per contrassegnare quelli già visitati) durante l'iterazione, ma non bisogna mai modificare la lunghezza di una lista durante un ciclo for. Un trucco di codifica sicuro consiste nel codificare temporaneamente due valori in un singolo intero (ad esempio usando il bit del segno) per simulare un booleano aggiuntivo per ogni elemento senza allocare spazio extra. Questa tecnica compare in problemi come 'find all numbers that disappeared in an array.'
def find_disappeared(nums):
# Mark visited by negating the value at the index
for n in nums:
idx = abs(n) - 1
if nums[idx] > 0:
nums[idx] *= -1 # mark as seen
# Indices with positive values are missing
return [i + 1 for i, v in enumerate(nums) if v > 0]
print(find_disappeared([4, 3, 2, 7, 8, 2, 3, 1]))
# [5, 6] -- O(n) time, O(1) extra spaceChecklist dei pattern per i colloqui sugli array
Prima di scrivere il codice per un problema sugli array, è utile passare in rassegna questa checklist mentale:
- L'array è ordinato? (consente di usare due puntatori e la ricerca binaria)
- Gli elementi sono compresi in un intervallo limitato (ad esempio 1..n)? (consente trucchi basati sugli indici)
- È richiesto operare sul posto? (puntatore di lettura-scrittura o scambi)
- Servono tutte le coppie o soltanto una? (determina se i cicli annidati sono accettabili)
- Casi limite: array vuoto, un solo elemento, tutti i valori uguali
def max_profit(prices):
# Pattern: single scan, track running minimum
# Time: O(n), Space: O(1)
if not prices: return 0 # edge case: empty
min_price = prices[0]
max_prof = 0
for price in prices[1:]: # start at index 1
max_prof = max(max_prof, price - min_price)
min_price = min(min_price, price)
return max_prof
print(max_profit([7, 1, 5, 3, 6, 4])) # 5
print(max_profit([7, 6, 4, 3, 1])) # 0Algoritmo di Kadane: sottoarray con somma massima
L'algoritmo di Kadane trova il sottoarray contiguo con la somma massima in tempo O(n) e spazio O(1). A ogni passaggio, occorre decidere se estendere il sottoarray corrente o iniziarne uno nuovo: current = max(num, current + num). Se current + num è minore di num da solo, il sottoarray corrente sta riducendo la somma e bisogna ricominciare da zero. Mantenere il massimo globale durante tutta la scansione.
def max_subarray(nums):
current = global_max = nums[0]
for n in nums[1:]:
current = max(n, current + n) # extend or restart
global_max = max(global_max, current)
return global_max
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# 6 (subarray [4, -1, 2, 1])
print(max_subarray([-1, -2, -3]))
# -1 (all negative: take the least negative)Verifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: gli array offrono accesso casuale in O(1), ma inserimenti ed eliminazioni nel mezzo in O(n): conoscere questa asimmetria guida la scelta dell'algoritmo, il pattern del puntatore di lettura-scrittura rimuove elementi o sposta valori sul posto in tempo O(n) e spazio O(1) e la codifica tramite bit del segno e i trucchi che usano l'indice come contrassegno consentono soluzioni in spazio O(1) a problemi che altrimenti richiederebbero un array ausiliario. Successivamente verranno esaminate le somme prefisse e i totali progressivi.
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 30
- Lezioni
- 120
Domande Frequenti
La lezione «Basi degli array e operazioni in-place» è gratuita?
Sì — il testo completo di «Basi degli array e operazioni in-place» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Basi degli array e operazioni in-place»?
Ripassi l'indicizzazione e la mutazione e analizzi le insidie più comuni degli array nei colloqui, come gli errori off-by-one e la modifica di una lista durante l'iterazione Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Basi degli array e operazioni in-place»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Basi degli array e operazioni in-place
- Somme prefisse e totali progressivi
- Due puntatori: estremità opposte
- Due puntatori: lento e veloce