Ezt a feladatot hogy kéne megoldani?
Az a feladat, hogy bemenetül kapok egy pozitív számokból álló integer tömböt és vissza kell adnom egy integer tömböt, ahol az i-edik elem értéke az, hogy a bemeneti tömbben az i-edik indexen lévő elemnél hány kisebb elem van a tömbben.
Például ha {2, 5, 1} a bemeneti tömb, akkor {1, 2, 0} a kimenet mert a 2-nél 1db kisebb elem van, 5-nél 2db kisebb elem van, 1-nél pedig 0db kisebb elem van a tömbben.
Az jó megoldás ha 2 egymásba ágyazott for ciklussal megvizsgálok minden párt és ha a külső értéknél kisebb a belső, akkor növelem a kimeneti tömb megfelelő indexét?
(a nyelv mindegy, az megoldás elve a lényeg nekem)
válasza: válasza:Attól függően, hogy milyen szintű feladat, teljesen jó.
Esetleg csinálhatsz egy segédtömböt, amibe a bemeneti tömb elemeit rakod sorrendbe rakva, majd azon az adott elemre bináris keresést végrehajtva, a megtalált elem indexéből következtethetsz az adott számnál kisebb elemek számosságára.
Via: [link]
válasza:Te írtad ki a prefix sum kérdést?
Ha nem, akkor annak nézz utána, mert ez klasszikus prefix sum probléma.
Ha kicsi a tömb elemszáma, akkor egyébként jó lehet a négyzetes megoldásod is.
válasza: válasza:Én hirtelen ezt tudtam rá összehozni: [link]
Nem igényli a rendezést (annak is van költsége) és a négyzetnek csak a felét járja be.
válasza:Vannak megkötések az elemszámra, vagy a maximális előforduló értékre, vagy bármi másra?
Ilyen információ hiányában nem igazán lehet optimális megoldást mondani.
Egy prefix sum megoldásnál pl. O(n + k) a time és a space is. Ha pl. k nagy, akkor kellően kis elemszám esetén jóval lassabb lehet akár egy négyzetes megoldásnál is.
"a számok [1,100] intervallumban fordulhatnak elő, a tömb mérete pedig 10^6 lehet maximum"
Ezek vannak.
Köszönöm az eddigi válaszokat.
válasza:Hát akkor egyértelműen prefix sum.
Ha 32 bites intekkel számolunk, akkor legrosszabb esetben 4MB körüli extra memória kell neki és mondjuk nagyságrendileg 30 ms futásidő (ez nyilván sokmindentől függ).
Egy négyzetes megoldás órákig futna.
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!