Mi a legjobb futásidő és memória komplexitás ami elérhető ennél a Java feladatnál?

"Ez így asszem O(n) idő és O(n) memória. lehet valamelyiket tovább csökkenteni?"

A space-t lehet konstansra.

Mivel 1-től n-ig fordulnak elő a számok, így minden szám megfeleltethető a tömb egy indexének.

Végig mégsz a tömbön és az előforduló számoknak megfelelő indexeket megjelölöd, aztán végig mész mégegyszer és ha egy index nincs megjelölve, akkor növeled eggyel az eredményt.

És hogyan jelölöd meg az indexeket, ha nem hozhatsz létre egy másik tömböt?

És hogyan számolod meg őket egy bejáráson belül? Amíg a megjelöléssel nem értél a végére, nem tudhatjuk, melyik indexnél kell eggyel növelni az eredményt.

"És hogyan jelölöd meg az indexeket, ha nem hozhatsz létre egy másik tömböt?"

Negatívra állítom az értéküket.

"És hogyan számolod meg őket egy bejáráson belül? Amíg a megjelöléssel nem értél a végére, nem tudhatjuk, melyik indexnél kell eggyel növelni az eredményt."

Az egy bejárásos megoldásnál nem a megjelölteket számolnám.

Tudom, hogy N szám van összesen, tehát ha megjelölök egyet, akkor már csak N - 1 hiányozhat. Ha megjelölök mégegyet, akkor már csak N - 2 és így tovább. Ha a tömb végére érve megjelöltem M indexet, akkor N - M a megoldás.

Két körös megoldás olyan szempontból jobb, hogy ott vissza lehet állítani a tömb eredeti állapotát (ha szükséges, a kérdésben nincs erre vonatkozó megkötés), egy körös megoldásnál nem.

Vagyis ha mondjuk n=25 és az első tag 24, akkor a 24-es indexű tagot átállítod pl. -1-re, jól értem? Hogyan fogod akkor figyelembevenni azt, amelyik eredetileg a 24-en volt?

De még ha működne is elfogadhatatlan egy ilyen függvénytől, hogy megsemmisíti a tömböt. Miért akarnánk tudni egy tömbről, hogy hány különböző eleme van, ha nem akarunk vele tovább dolgozni? Íratlan szabály, hogy ha a feladat célszerűsége nem foglalja magában, vagy nincs külön megengedve, akkor nem módosítjuk a kapott adatszerkezeteket.

Úgy érzem, mintha egy óvodásnak magyaráznám a differenciálszámítást.

Mi a fenéért állítanám a 24-et -1-re? Ha 24 egy érték, akkor -24, re állítom. Így bármikor visszakaphatom az eredeti értéket.

Azt is külön kiemeltem, hogy a 2 körös megoldásnál visszaállítható az eredeti tömb, 1 körben nem (bár utána ott is bármikor, egy újabb körben).