Pentru că ne place algoritmica, revenim cu o problemă relativ simplă: Se dă un array de numere, conținând exact n numere distincte din intervalul [0, n]. Se cere să se găsească numărul lipsă. Se garantează faptul că întotdeauna un singur număr va lipsi. Se consideră că n are tipul int.
Haideți să luăm și câteva exemple:
- array = [4, 0, 1, 2]. Observăm că n = 4 și numărul lipsă este 3.
- array = [0, 2, 4, 3, 5, 6]. Observăm că n = 6 și numărul lipsă este 1.
Să notăm cu X numărul lipsă. Dacă n = 4, vom avea numere din intervalul închis la ambele capete [0, 4], adică 0, 1, 2, 3, 4. Din școala generală ne aducem aminte că dacă le adunăm pe toate vom obține 10 = n x ( n + 1) / 2 = 4 x 5 / 2 = 10. Ni se garantează faptul că un singur număr lipsește și toate celelalte vor fi prezente în array-ul nostru. În acest condiții, putem să adunăm toate numerele din array, să determinăm valoarei lui n și să determinăm necunoscuta X ca fiind diferența între suma toturor numerelor de la 0 la n și suma obținută de noi.
Aplicând algoritmul de mai sus în cazul primului examplu vom avea:
- suma tuturor numerelor de la 0 la n (n = 4) ca fiind 10.
- suma tuturor numerelor din array-ul dat = 7.
Pasul următor este să facem diferența între 10 și 7 și vom avea fix numărul lipsă - 3. Soluția noastră va avea o complexitate de timp liniară și o complexitate de spațiu constantă. De ce? Pentru că trebuie să iterăm o dată peste toate valorile din lista primită ca și input și în plus nu avem nevoie de nicio structură de dată adițională de tipul List sau Map pentru stocarea unor date intermediare.
O altă idee de implementare este să sortăm lista de valori primită ca și input crescător. După ce am făcut sortarea, putem să iterăm peste valorile obținute și să determinăm ușor numărul care lipsește. Dacă ar fi să evaluăm această soluție, am ajunge la concluzia că are o complexitate de timp = O(nlogn), dată de algoritmul de sortare - quicksort și o complexitate spațială liniară - O(n) asta dacă nu ni se permite să modificăm lista inițială. Să zicem că lista inițială este imutabilă.
O altă idee este să folosim un HashSet pentru a stoca valorile din lista inițală. Prima fază este să inițializăm set-ul cu valorile din listă, după care să iterăm de la 0 la n și să căutăm elementul care nu se află în set. Analizarea acestei soluții ne conferă o complexitate de timp liniară și una de spațiu tot liniară.
Spor la implementare!
