Milyen algoritmussal oldanád meg az alábbi feladatot?
Üdv. Ez egy (újabb) olyan feladat vagy kihívás, ahol a lényeg, hogy a programnak a lehető leggyorsabban kell lefutnia.
Programnyelvet tekintve tetszőleges, de célszerű a sebesség miatt a C/C++ nyelvek használata.
Továbbra is igaz, hogy nem kódot kérek, hanem a kérdés, milyen algoritmussal, adatszerkezettel oldanád meg ezt a feladatot.
---------------
A feladat:
Egy számsorozatban csupa különböző egész szám van.
Írj programot, amely megadja az egymástól legmesszebb levő két elemet, amelyek közül az első
nagyobb, mint a második (azaz rendezés után ellenkező sorrendben lennének)!
Bemenet
A standard bemenet első sorában az elemek száma van (1 ≤ N ≤ 500 000).
A következő sorban az N különböző pozitív egész szám található (értékük legfeljebb 10 millió).
Kimenet
A standard kimenet első sorába a két legmesszebb levő elemnek az értékét kell írni, amelyek közül az első nagyobb, mint a második! A második sorba ezen két elemnek a távolságát. Több megoldás esetén bármelyik kiírható.
Rendezett sorozat esetén egyetlen -1-et kell kiírni!
Példa 1:
Bemenet
10
7 2 4 17 6 5 13 10 18 19
Kimenet
7 5
5
Példa 2:
Bemenet
10
4 10 17 15 14 28 9 25 9 11
Kimenet
10 9
7
Korlátok:
Időkorlát: O(n) vagy O(n logn)
O(N^2) megoldás nem fogadható el.
Memórialimit: 32 MB
válasza:Javítottam, az összes ide kiírt inputra meg még más inputokra is kipróbáltam mielőtt közzé tettem ide : [link]
A max_dist2 függvénybe rossz sorba írtam a d = j - i értékadást ez volt a hiba az előzőbe, ha szigorúan a korábban felvázolt specifikációhoz mérem. Viszont ha ezt a mondatot ne írtad volna bele : "A bemeneti tombot el is felejthetjuk." akkor azt mondom hogy teljesen igazad van. Ugyanis ez arra utal, hogy a bemeneti tömböt fel se használjuk sehol a pMax és sMin kiszámítása után az algoritmusba. Ez azonban nem igaz mert pl.:
Ennél az inputnál :
2 6 4 8 1 5 7 10 3 9
ezt a p_max-ot számolja : [2, 6, 6, 8, 8, 8, 8, 10, 10, 10]
A harmadik 10-es "mögött" egy 9-es van amit nem tud(na) az algoritmus, ha eldobjuk(eldobnánk) a bemeneti tömböt, hogy az már több mint 6, így helytelen megodást ad(na). (Persze pont, hogy felhasználom benne a bemeneti tömböt is, hogy ne adjon rossz megoldást.)
válasza: válasza:Szerencsetlen gyerek meg mindig azt hiszi, hogy specifikaciot irtam.
"Viszont ha ezt a mondatot ne írtad volna bele : "A bemeneti tombot el is felejthetjuk." akkor azt mondom hogy teljesen igazad van. Ugyanis ez arra utal, hogy a bemeneti tömböt fel se használjuk sehol a pMax és sMin kiszámítása után az algoritmusba. Ez azonban nem igaz"
De igen, igaz, onnantol nincs szuksegunk az eredeti tombre. Te feleslegesen hasznalod, de toled mar ez is szep teljesitmeny, hogy egyaltalan mukodik, miutan a szadba lett ragva a megoldas.
válasza:"Úgy látom konkrétan leírta a 15-ös válaszban, hogy ez a probléma a kódoddal. Gyakorlatilag le lett diktálva neked a megoldás :)"
Akkor nem figyeltél eléggé. A konkrét lediktálásba beletartozik az a konkrét d változó értékadás sorcseréje is. A konkrét okosság sincs ledikálva milyen módon áll elő az input tömb felhasználása nélkül s_min és p_max kiszámítása után. Nem kívánom folytatni még mitől nem konkrét lediktálás. Ezen kívül bölcsebb lett volna, ha ezt nem írod ide, semmit nem ad hozzá, te semmit nem szóltál hozzá érdemben amitől többet megtudna a témával kapcsolatban bárki aki olvassa.
"Szerencsetlen gyerek meg mindig azt hiszi, hogy specifikaciot irtam."
Te pedig EQ-ból (Emotional Quotient) nem muzsikáltál valami fényesen ezzel a beszólással, én nem személyeskedtem. Ha meg tanító jelleggel írtad a dolgokat, akkor meg nem vall annyira bölcs és nemes lelkű tanítóra, hanem inkább egy érzéketlen nagyképűre vall.
"Mobilról vagyok, de így ránézésre ..." ha még hozzá tetted volna nekem, hogy biztos vagyok e benne, hogy minden érték adó utasítás jó helyen van e, akkor úgy gondolnám, hogy neked arányban van a nagyképűséged a tudásoddal.
Hogy érdemben a témával kapcsolatban is írjak valamit a 3 max_dist implementációm : [link]
válasza: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!