minimalna liczba dodatnia nieobecna w tablicy

0

Cześć,

Zadanie brzmi - napisz metodę która:

  • dla nieposortowanej, duzej tablicy zawierającej wartości int
  • zwróci najmniejszą liczbę dodatnią, która nie wystąpiła w tablicy wejściowej

np.
1,2,3 --> 4
1,3,4 -->2
-1,2,1,1,3,6 -> 4
2,3,4,5 --> 1

Implementacja w czymkolwiek... - da się osiągnąć lepszy wynik niż O(n) ?

1

Co to za pytanie? o_O Oczywiście że nie da się szybciej niż O(n) bo póki nie sprawdzisz wszystkich liczb w tablicy to nie masz pewności która liczba w niej nie wystąpiła...
Ale ciekawi mnie czy masz pomysł na liniowe rozwiązanie, bo z treści zadania wynika że:

  • zakresem jest int
  • wejściowa tablica zawiera dużo liczb
    Co oznacza że zliczanie / ładowanie danych do HashSeta raczej odpada bo pesymistycznie możemy mieć MAX_INT różnych liczb na wejściu.
0

Chwila w internecie http://www.geeksforgeeks.org/find-the-smallest-positive-number-missing-from-an-unsorted-array/
A O(n) time and O(1) extra space solution

0

Już wyjaśniam.... a może najpierw moja implementacja:

    public int findMinPositiveValueNotExists(final int[] array) {
        Integer out = 1;
        for (Integer i : array) {
            if (i > 0 && i == out) {
                out++;
            }
        }
        return out;
    }

Z kilku, kilkunastu testów, które wykonałem wynika, że jest poprawna (a przynajmniej nie znalazłem przypadku danych wejściowych, który by temu zaprzeczał) - może któryś z Kolegów byłby w stanie taki wskazać (dodam że przypadek Integer [] i null jako value pomijamy)?

Wymaga jednokrotnego przejścia przez tablicę, więc złożoność O(n).

Zastanawia mnie, czy to może być aż tak proste :) (porównaj z algorytmami na przytoczonej stronie, nie mówiąc o angażowaniu kolekcji)
(ponadto warunek i>0 można nawet pominąć - ale zostawiłem dla zachowania zgodności)

0

@murmi lol toś wymyślił algorytm. Sprawdź sobie dla odwrotnie posortowanej tablicy...
Przecież jak znajdziesz "1" na samym końcu to skad będziesz wiedział czy 2 juz była czy jeszcze nie? o_O

0

tiaaaaaaa - właśnie do mnie dotarło i chciałem sam siebie skrytykować, ale mnie ubiegłeś :) {3,2,1}

widzisz..... na kilku (wydawało się) pseudolosowych danych wejściowych zadziałało i mnie zmyliło ;)

EOT

0

Zacznij jak sortowanie przez wybór dopóki różnica między elementami jest większa od jeden. Pesymistycznie kwadrat, lecz przynajmniej będziesz miał coś poprawnie działającego na czym będziesz weryfikować swoje inne rozwiązania.

0

Co sądzicie o

def znajdz(tab):
	byly = [False for x in range(32767)]
	for liczba in tab:
		if liczba > 0:
			byly[liczba] = True
	for i in range(1, 32767):
		if byly[i] is False:
			return i
	return 0
 

Powinien być w miarę szybki, ale trochę pamięci na dodatkową tablicę zje.
Zakładając naturalnie że int ma "standardowe" 16 bitów ze znakiem, bo z tym też różnie może być

0

@sig czytaj mój pierwszy post -> pisałem że zwykłe zliczanie raczej słabo działa bo int to ma raczej 32 bity a nie 16 ;) Więc twoja tablica ma już kilka GB... ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1