Mi az optimális algoritmus tömbben egyszer előforduló elem megkeresésére?

Esetleg rendezni, majd párosával összehasonlítani.

(1,1),(2,3),(3, )

^

(5,5),(6,8),(8, )

^

"Menjek végig a tömbön és számoljam az egyes elemek előfordulását" szerintem ez sem O(n).

Egy másik ötlet:

Elindulsz a 2. elemtől a tömb végéig, majd megnézed van-e olyan ami egyezik az első elemmel, ha van a 2. elemmel lévővel kicseréled és utána a 4. elemtől hasonlítasz a 3. elemmel és így tovább. Ha nincs akkor meg van a keresett elem:

1. lépés után: 1,1,3,2,3

2. lépés után: 1,1,3,3,2

3. lépés után: 1,1,3,3,2 <- a '2' volt az adott elem

Persze asszociatív tömbbel lehetséges pl.:

counts['-1567'] := counts['-1567'] + 1;

és megnézni hol van 1.

"Annyi módosítás, hogy a számok mégsem 0-9 intervallumban lehetnek, hanem mondjuk 32 bites számokig bezárólag, ha befolyásol ez valamit."

Hát ez elég sokat befolyásol... 0-9 esetben csak meg kell számolnod hogy melyikből mennyi van és utána a 10-es listából kivenni azt ahol 1 az érték... Ha bármilyen szám lehet, akkor ezt nem tudod megtenni (illetve lényegesen több memória kell és a végső kiválasztás is végig kell hogy menjen a 4 milliárd elemen...)

>"Menjek végig a tömbön és számoljam az egyes elemek előfordulását, aztán utána menjek végig az előfordulásokon és az 1-es előfordulással térjek vissza?"

Nekem is ez jutott eszembe.

>"A számok 0-9 intervallumban vannak"

Ha ilyen aránylag kevés féle elem van, akkor csinálhatsz egy külön 10 elemű (0..9) tömböt, amiben számlálod az adott elem előfordulását. Utána igen, ezen a 10 elemű tömbön is végig kell menni, hogy melyik lett 1 db-os, de az eredeti tömbön legalább csak egyszer kell végigszaladni.

O(n+m) // m: elemtípusok száma