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

"Utóbbinál nem érhető el jobb komplexitás, hiszen minden elemet érinteni kell, tehát ez az optimális megoldás."

Miért kellene?

#16 Ötletes, tetszik!

Bitműveletekkel jól működhet, de a valódi Python Set bővítés-törlés erősforrásigényes lenne. + Akkor működik, ha egy darab páratlan előfordulást kell keresni, de a példa épp ez, úgyhogy én megvettem. :)

"Miért kellene?"

Rendezetlen listában egyetlen esetben nem kell, ha az utolsó előtti elemig minden elem kétszer fordult elő, ..de még ilyenkor is praktikus kiolvasni, hogy melyik az egyszer előforduló utolsó elem, mert gyorsabb, mint kitalálni. Minden más esetben a legutolsó elemtől is függ, hogy mi az eredmény.

off

"optimális algoritmus"

Ez nemrég külön vita tárgya volt, hogy mi az az "optimális". A lényeg, hogy ez függ az elvárásoktól, feltételektől. Szerintem te az ideális algoritmust keresed. :)

Na de ez a kérdés (pontosabban az előfeltétel):

"Ha van egy elem a tömbben, ami csak egyszer fordul elő és minden más elem kétszer."

Ebből következik, hogy elég addig vizsgálni, amíg elő nem bukkan a páratlan elem, nem kell a tömbön végig menni.

" Ez csak akkor igaz, ha rendezett a tömb, de itt nem volt ilyen kiinduló feltétel."

Hogy lenne ez igaz?

A tömbön akkor kellene teljesen végigmenni (több ízben (tehát minden elemet feldolgozni)) ha a páratlan elem lenne az utolsó. Ez a lehető legrosszabb eset.