Hogyan lehetne tovább optimalizálni ezt a megoldást?
Az a feladat, hogy tömbben kell megkeresni a legtöbbször előforduló elemet. A nyelv igazából mindegy, Pythonban írtam, de megértek mást is.
A tömbnek ilyen tulajdonságai vannak:
- minimum 3 elemű, maximum 10 000 elemű
- az elemek a [0, tömb mérete[ intervallumból vehetnek fel értékeket, tehát 100 elemű tömbben például 0-99 elemek lehetnek, 5000 eleműben 0-4999 stb.
- mindig van jó megoldás és mindig csak egy jó megoldás van, tehát a legtöbbször előforduló elemen kívül minden más elem kevesebbszer fordul elő
Példa és megoldás:
[4, 0, 0, 3, 1] - 0 (kétszer fordul elő)
[4, 0, 9, 2, 4, 4, 9, 0, 3, 7] - 4 (háromszor fordul elő)
[1, 1, 2] - 1 (kétszer fordul elő)
A megoldásom 2 körös, első körben végig megyek a tömbön és dictben (más nyelvekben hashmap, hashtable) letárolom az elemeket az előfordulásukkal.
A második kör pedig egy maximum keresés a dictben, tehát megkeresem a legnagyobb előfordulást és visszaadom az ahhoz tartozó elemet.
Lehet ezen a megoldáson javítani valahogy?
Ha jól gondolom ez O(n) idő és O(n) tár komplexitás ebben a formában (mert minden elemen végig kell menni, a dictbe pedig legrosszabb esetben tömb mérete - 1 elem kerül).
Nem feltétlenül kódra vagyok kíváncsi, ötletekre főleg.
válasza:Köszi a választ.
"Nem dictionaryben, hashmapben tárolod a darabszámokat, hanem sima tömbben. Nyilván ez több memóriát kíván"
Miért kíván nyilván több memóriát?
Ha jól tudom tömbben csak maga az érték tárolódik, dictben/hashmapben pedig a hash is, tehát azonos elemszám esetén az utóbbinak minimum 2x annyi memória kell.
Tehát ha a dict/hashmap mérete eléri a tömb felének a méretét, már egálban vannak és e fölött pedig már többet foglal a hashmap.
válasza: válasza:#3 nem írtam sehol, hogy O(n)-nél jobb komplexitást szeretnék (bár lehet félreérthetően fogalmaztam ezek szerint?)
Viszont ha egy for ciklusban ezerszer végig mész a tömbön, az is O(n) komplexitás.
Nem jelenti azt, hogy a konstans faktoron nem lehet javítani.
válasza:Ha az egyik elem előfordulása meghaladja a tömb hosszának felét vizsgálat közben, akkor biztos ő a legtöbbször előforduló elem.
Pl a harmadik példánál elég a második elemig vizsgálni.
válasza:#6 nem vagyok biztos benne, hogy ez megéri.
Így ugye minden egyes elemnél +1 vizsgálatot kell végeznünk (összehasonlítani a darabszámot a tömb méretének felével).
Tehát pl. abban az esetben, ha nincs olyan elem, ami a tömb felének méretéhez képest többször fordul elő, akkor feleslegesen végeztünk n darab összehasonlítást.
De még ha van is olyan elem, n/2-szer akkor is el kell ezt a vizsgálatot végeznünk, tehát összességében talán a maximum kiválasztást lehet így megspórolni.
Mindenesetre érdemes elgondolkodni rajta, köszönöm, ment a zöld.
válasza:"az elemek a [0, tömb mérete[ intervallumból vehetnek fel értékeket"
Ez a feltétel igen hasznos, azon gondolkodj el, hogy ezt milyen formában tudnád felhasználni.
*Spoiler*
1-pass, O(n) time, O(1) space megoldás:
https://pastebin pont com/bufcrVNC
(elképzelhető, hogy 2 pass gyorsabb lenne valamivel, benchmark nélkül nem tudom megmondani)
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!