[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

[Hipodups]

@NotABigFan: rozwiązanym to tak - liniowo iteruje po tablicy. Wyszukuje maxa. Następnie sprawdzam czy max jest większy od 0 , jak tak to max +1 a jak nie to to 1.

[nesti32]

@Hipodups: No chyba nie, wez pod uwage taka tablice [-1,-3, 1, 2, 3, 5]. Szukana liczba jest tu 4 nie 6.

[Saly]

@NotABigFan czy n to rozmiar tablicy czy zbioru liczb? Jak to pierwsze to wystarczy sprawdzać linowo czy kolejne liczby naturalne są w tablicy

[S.....s]

@NotABigFan: hmm no więc
na początek można zauważyć, że jak mamy tablicę z n liczbami, to szukamy liczby z zakresu 1 - n (ewentualnie n+1)
może by tak przeiterować po tablicy, i jeśli liczba x jest w zakresie 1;n to w indeksie x - 1 coś zaznaczamy, zerujemy, negujemy czy coś i po przejściu jedziemy jeszcze raz po tablicy, i pierwszy element, który spełni jakiś warunek będzie odpowiedzię, ewentualnie n+1

[S.....s]

@NotABigFan: ale nie chce mi się myśleć nad kodem czy konkretnym rozwiązaniem xd

[exother]

@SuppressWarnings: ok, tylko jeszcze pamięć O(1) ( ͡° ͜ʖ ͡°)

[S.....s]

@exother: pamięć O(1) już jest (chyba że tablica wejściowa też się liczy) xd

[exother]

@SuppressWarnings: nie wiem czemu, ale przeczytałem, że chcesz osobną tablicę, jest w porządku :)

edit: tylko trzeba pamiętać, że wcześniej możesz mieć odwołanie to indeksów, których jeszcze nie odwiedziles i poskakac trochę po tablicy

[NotABigFan]

@Saly: rozmiar tablicy, jak to sprawdzanie ma działać liniowo?
@SuppressWarnings: jesteś na dobrym tropie ale @exother ma rację trzeba to jeszcze dopracować

[Saly]

@NotABigFan:
def foo(x):
i = 1
while True:
if i not in x:
return i


[NotABigFan]

@Saly: in szuka liniowo w tablicy (czy nie?). Czyli to będzie działać ok O(n^2)

[D.....n]

@NotABigFan:
Dla kolejnych elementów tablicy robimy tak:
- jeśli tab[i] <= 0, to nic nie robimy (traktuję takie miejsca jako "puste")
- w p.p. bierzemy x = tab[i] i dalej
-- jeśli x > większe od rozmiaru tablicy, to je "usuwam", tzn. robię tab[i] = 0
-- w p.p. wrzucam x w tab[x], czyli chciałbym, żeby każdemu odpowiadało jego miejsce w tablicy, a tab[i] czyszczę (ustawiam

[Saly]

@NotABigFan: tak, ale zakladajac, ze zbior liczb jest staly mamy n*C, czyli O(n)

[S.....s]

@Saly: tam masz n^2

[NotABigFan]

@Demolicjon: Zgadza się ( ͡° ͜ʖ ͡°) gratsy.

[D.....n]

@Saly: Nieprawda. Nie masz górnego limitu na wartość liczb, zwłaszcza w takich pajtonach ze wsparciem dla bignumów. W najlepszym przypadku możesz zauważyć, że jeśli po n iteracjach algorytm nie zakończył działania, to brakuje liczby n+1, co z miejsca daje O(n^2)

[Saly]

@SuppressWarnings: n*c, rozmiar zbioru liczb nie zalezy w zaden sposob od n, wiem nie wiem skąd tam n*n

[D.....n]

@Saly: ^

[S.....s]

@Saly: ee co? zarówno tablica jak i zbiór rozwiązań są wielkości n