Mi az optimális algoritmus tömbben egyszer előforduló elem megkeresésére?
Ha van egy elem a tömbben, ami csak egyszer fordul elő és minden más elem kétszer.
Pl. [1, 2, 3, 1, 3] tömb esetén a 2 lesz az eredmény, [8, 8, 5, 5, 6] esetén pedig a 6.
A számok 0-9 intervallumban vannak.
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?
Vagy van ennél jobb megoldás?
(Pythonban csinálom, de mindegy a nyelv igazából)
válasza:#30 azt javaslom nézz utána az aszimptotikus komplexitás fogalmának (mert algoritmus komplexitásánál azt vizsgáljuk).
Az általad leírt "legrosszabb eset" pedig egyébként az, ha az első elem a páratlan, nem az utolsó.
válasza:"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"
Nem az elem páratlan, hanem az elem páratlan számú esetben fordul elő a tömbben... (Konkrátan 1 esetben, míg a többi 2 esetben).. de olvasd el a feladatot...
Ehhez végig kell menni a teljes tömbön minden esetben ha nem rendezett), hisz az utolsó előtti elem esetén anynit tudunk, hogy melyik az a 0 vagy 2 szám, ami addig 1x foldult elő...
Egyébként ajánlom figyelmetekbe az ehhez hasonló problémát:
Minden elem 3x fordul elő, és 1 elem 1x... ez is megoldhato 1x-i végigjárással, de már bonyolultabb.
válasza:"Nem az elem páratlan, hanem az elem páratlan számú esetben fordul elő a tömbben"
Ok, akkor félreértettem a feladatot.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!