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

az hogy egy elem szerepel-e egy rendezetlen tömbben az O(n) (legrosszabb eset)

, de mivel nem egy elemet kell nézni ezért jóval rosszabb futásidejű lesz

"minden más elem kétszer"

Sztem elsiklott mindenki e-felett? Hát így baromi egyszerű, csak XOR-old össze mind egymás után.

Épp meg akartam kérdezni, hogy tudjuk-e a többször előforduló elemekből hogy páros vagy páratlan darabszámú van-e... mert ha mind páros, vagy pl mindegyikből 3 van, akkor gyorsan meg lehet oldani.

Azt kell kihasználnod, hogy minden más elem kétszer fordul elő.

Könnyen érthető O(n)/O(n) (time/space) megoldás:

- definiálsz egy Setet (azért Set, mert O(1) add, contains és remove műveleteket akarunk)

- végig iterálsz a tömbön, ha adott elem már benne van a Setben, akkor törlöd belőle, ha nincs, bele rakod

- a végén egy elem marad a Setben, az egyszer előforduló

O(n)/O(1) bit manipuláció:

Simán össze XORzod az elemeket, kihasználva, hogy a XOR asszociatív és kommutatív.

Pythonban valami ilyesmi:

def findSingle(nums):

s = 0

for num in nums:

s ^= num

return s

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