[NotABigFan]

Czołem Wielkiej Polsce! Dzisiaj zadanko od Stripe.

Dana jest tablica liczb całkowitych. Znajdź najmniejszą dodatnią liczbę całkowitą, której nie ma w tablicy. Tablica może zawierać duplikaty oraz liczby ujemne. Można modyfikować tablicę. Czas O(n), pamięć O(1)

np:

[] -> 1
[-1, -2, -3] -> 1
[1, 0, -1, 2] -> 3

#dailycodingproblem #programowanie

[Frogof]

@NotABigFan: nie czytałem komentarzy. Dwa przypadki: albo min - 1 jeśli min to nie 1, albo counting sort ignorujący wszystko mniejsze od 1 i nie mieszace się w tablicy.

[NotABigFan]

@Frogof: Czasowo by się zgadzało ale w jaki sposób ten counting sort ma zużywać stałą pamięć?

[Frogof]

@NotABigFan: sortuje tylko od 1 do n+1, resztę ignoruje. Wcześniej jeszcze trzeba raz przejść i ustawić wszystkie wartości spoza zakresu na 1. W razie konfliktu (nadpisanie czegoś czego jeszcze nie posortowalem) to używam wartości ujemnej żeby takie pole oznaczyć.

[NotABigFan]

@Frogof: Szczerze to dalej nie jarze jak nadpiszesz coś czego jeszcze nie posortowałeś, że tego nie zgubisz. Counting sort używa minimum O(k) pamięci jeżeli sortuje liczby od 1 do k czyli jeżeli chciałbyś naprawdę zliczać liczby w tablicy to potrzebowałbyś do tego O(n) pamięci w tym przypadku.

[Frogof]

@NotABigFan: po zmianie wszystkiego ujemnego i większego od n na 1 sortuje w miejscu. Jak chce nadpisać jakieś pole którego jeszcze nie sortowalem to zmieniam znak. Np. w a[6] znajduje 8, w a[8] 9. Wiec a[8] zmianiam na -9. W ten sposób oznaczam ze jest tam nieposortowane 9 i posortowane 8. Po przejściu całej tablicy pierwszy indeks dla którego wartość w tablicy to 0 to moja odpowiedz.

[NotABigFan]

@Frogof: Ok wiem o co Ci chodzi to jest mniej więcej jak wygląda właściwe rozwiązanie ale to nie jest counting sort w żadnym wypadku bo nie zliczasz ilości wystąpień tylko flagujesz liczby z zakresu

[Frogof]

@NotABigFan: no tak dokładnie to nie jest ani jedno ani drugie, bo musisz oznaczyć te nadpisywanie, ale to ze zliczam niczego nie zmienia, wiec po wykonaniu counting sorta z ta modyfikacja wyżej otrzymuje rozwiązanie:)