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)
@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.
@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
@Saly: rozmiar tablicy, jak to sprawdzanie ma działać liniowo? @SuppressWarnings: jesteś na dobrym tropie ale @exother ma rację trzeba to jeszcze dopracować
@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: 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)
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
Komentarz usunięty przez autora
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
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
@SuppressWarnings: jesteś na dobrym tropie ale @exother ma rację trzeba to jeszcze dopracować
def foo(x):
i = 1
while True:
if i not in x:
return i
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