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: válasza:"Egy számsorozatban csupa különböző egész szám van"
A 2. példában 2x szerepel a 9. Most akkor lehet ismétlődés, vagy nem?
#3 Valóban a 2. példa hibás.
Az 1. példa helyes, de akkor itt van még 2 példa:
Bemenet
20
2 29 32 26 23 9 39 8 30 12 22 31 13 5 6 1 36 4 19 7
Kimenet
29 7
18
-----------
Bemenet
10
2 6 4 8 1 5 7 10 3 9
Kimenet
6 3
7
válasza: válasza:Bocsi, hogy így beleszólok, úgy, hogy nem a kérdező vagyok.
De ha valakinek van O(n) megoldása, az nagyon érdekelne, egy ideje töröm rajta a fejem
Köszönöm a válaszokat.
#5 Egy kicsit részleteznéd? Pontosan nem értem mire célzol.
válasza:Vegyuk ezt a peldat:
7 2 4 17 6 5 13 10 18 19
Suffix min, O(N)-ben szamolhato:
2 2 4 5 5 5 10 10 18 19
Ez ugye azt mutatja meg, hogy az i-edik elemtol kezdodo suffix-ban (az i-edik elemet megelozo elemek a prefix, az minket nem erdekel) mi a legkisebb elem.
Az input minden egyes elemehez keressuk a suffix-ban azt az elemet, ami meg kisebb az aktualis elemtol es a legtavolabb van tole. Mivel a suffix tomb rendezett, igy ezt megtehetjuk binary search-el, O(logN) komplexitassal. Ezt N-szer hajtjuk vegre (minden egyes elemnel), igy O(NlogN) lesz a komplexitas.
Az O(N) megoldas osszetettebb, ha ezt nem erted, akkor arrol felesleges beszelni.
válasza:"Az O(N) megoldas osszetettebb, ha ezt nem erted, akkor arrol felesleges beszelni."
Nem a kérdező vagyok, de ezt értem (implenetáltam is python-ban ugyan), ment is a zöld kéz, viszont hogy van az O(N) megoldás? Egyszerűen nem jövök rá, már több mint 1 napja gondolkodom rajta.
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!