Ezt a Java feladatot milyen adatstruktúrával kéne megvalósítanom?
Olyan queuet kell csinálnom amibe inteket lehet rakni és mindig a legtöbbször előforduló intet adja vissza de egyébként queueként viselkedik.
Pl belerakom az 1, 2, 3 számokat ilyen sorrendben, akkor először az 1-et fogja visszaadni aztán a 2-t aztán a 3-at. De ha belerakom az 1, 2, 2, 3 számokat akkor először egy 2-t fog visszaadni aztán 1, 2, 3-at.
Ha több int is ugyanannyiszor fordul elő benne akkor szintén queuenak megfelelően a legkorábban bekerültet adja vissza először.
Pl ha 1, 2, 3, 3, 4, 4, 5 a tartalma akkor 3, 4, 1, 2, 3, 4, 5 sorrendben adja vissza az inteket.
Sima queueval ezt nem tudom megcsinálni de nem tudom mit lenne érdemes használnom helyette.
Illetve persze nem rendezett sorrendben fogja kapni az inputot csak a példákban írtam így.
De kaphat pl 5, 4, 2, 2, 6 számokat és ezeket ilyen sorrendben fogja visszaadni: 2, 5, 4, 2, 6 (először a kettest mert abból van a legtöbb aztán a többi elemet a bekerülés sorrendjében)
válasza:Nem hiszem, hogy van ilyen osztály beépítve, bár tévedhetek is.
Én a helyedben azt csinálnám, hogy leszármaztatok egy Queue-jellegű osztályból, ami implementálja a Deque és Queue interfészt, aztán override-olod a szükséges függvényeket.
Amit nem tudok az inkább az implementáció része.
Pl ha egy elemből több van mint a többiből akkor előfordulhat hogy a queue közepéről kell visszaadnom elemeket. Ezt hogy implementálom? Nem tudom azt sem hogy milyen formában tartsam nyilván az előfordulásokat pl.
Vagy ha bekerül egy új elem ami már a queueban van akkor honnan tudom hogy a régebbit kell majd először kivenni és honnan.
Az egésznek a logikáját nem tudom kitalálni.
Arra gondoltam hogy TreeSetet használok az elemek tárolására egy saját Comparatorral de nem tudom a Comparator hogy rendezzen hogy belekalkulálja az előfordulást és a sorrendet is.
Ettől nem jutok tovább:
válasza:Kiegészítettem a kódomat egy Mappel a dictionary javaslat hatására és raktam bele egy main függvényt is tesztelni de nem jó így sem.
1 2 2 3-at belerakva 2 1 null null-t ad:
válasza:TreeSet-et akarsz Queue-ként használni, de Set-ben ugye nem fordulhat elő adott elem egynél többször.
Illetve így az enqueue O(log n) komplexitást eredményez, holott optimális esetben az enqueue és a dequeue is O(1)-es művelet.
A Map egyébként jó irány, a TreeSet nem.
válasza:Bár nem java és nem biztos, hogy legoptimálisabb:
Köszönöm én a megoldásig sem jutottam el, ez alapján menni fog.
Majd megpróbálom optimalizálni is.
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!