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.
Ez elég erős, konstant memóriában eleve nem is gondolkodtam.
Köszönöm a választ, még emésztem kicsit :)
válasza:Azért egy kis csalás van a kódjában... hisz azt az üres területet használja ki, amit a számaid nem használnak...
Szóval ha pl 32 bites int-eket vannak a tömbben, de a tömb mérete csak 65000, akkor gyakorltilag a bitek fele üres... és ott számolja az értékeket... ez igazából pont ugyanaz mintha külön tömbben tennéd, csak elrejted...
Nem értem, hogy lehet bitek fele üres?
Egy 32 bites intben akkor is 32 bit van, ha 1 az értéke, meg akkor is, ha 2 147 483 647. Csak az egyes bitek értékei változnak.
válasza:üres = 0
tehát ha a tömböd <65536 méretű, akkor 16 bit tuti 0. Ott lehet mást csinálni.
Persze ez pont ugyanaz mintha 16 bites számokból állna az eredeti tömb és létrehoznál egy másik 16 bites tömbökből álló tömböt.
De minek hoznál létre mégegy tömböt, ha nincs rá szükség?
Nem ez a megoldása lényege?
Illetve ez miért "csalás"?
válasza:Azért csalás, mert nem biztos, hogy van ott hely...
Tegyük fel, hogy pl 200 méretű a tömböd..és byte[]-ben kapod a számokat. Akkor máris nem működik.
Tehát nem használ kevesebb memóriát, csak kihasználja, az esetlegesen üres részeket ami vagy van vagy nincs.
De hát nem byte[]-ban kapom a számokat.
(Python-ban eleve nincs is explicit byte adattípus)
Ott van eleve a feltételek között, hogy 10 000 elemű is lehet a tömb, egy (signed) byte-ba meg 127-nél nem fér nagyobb szám.
Meg mi az, hogy nem használ kevesebb memóriát? :)
Hogyne használna kevesebbet, ha nem hoz létre új tömböt?
Szerinted ha egy bit 0-ra van állítva, akkor az nem foglal memóriát, vagy mi?
válasza:Írtad, hogy a nyelv mindegy. Nyilván a 10000-es megkötés miatt a byte[] kiesik, de egy 16 bites szám tömb még lehetne más programozási nyelven.
Olyan memória területet használ, ami a paraméterként kapott tömbhöz tartozik. Nyilván mondhatod, hogy de ez már le van foglalva, nem kell újabb területet foglalni. Ezért írtam, hogy "csalás".
"Szerinted ha egy bit 0-ra van állítva, akkor az nem foglal memóriát, vagy mi?"
Ezzel nem tudom mint akarsz mondani, hisz a 0-k a paraméterként kapott tömben vannak, azt nem az algoritmus foglalja...csak használja.
válasza:Nem értem, ez egy programozási feladata, hogy jönnek ide egyáltalán a fair meg csalás fogalmak? :)
Ki mondta, hogy nem lehet módosítani a bemeneti tömbön?
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!