fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Számítástechnika » Programozás » Ennél a feladatnál lineáris...

Ennél a feladatnál lineáris keresés a jó megoldás? (Java)

Figyelt kérdés

Eltolt rendezett tömbben kell adott elemet megkeresnünk és visszatérni az indexével.

Pl. [4 5 1 2] a bemenet (az [1 2 4 5] eltolva kettővel jobbra) és az 1-et keressük, így 2-vel tér vissza a függvény. Az eltolás mértéke nem ismert.

Integer tömbről van szó, a mérete tetszőlegesen nagy lehet (a Java nyelv keretein belül) és nem tartalmazza ugyanazt a számot egynél többször.


Rendezett tömbnél ugye bináris keresés ugrik be, de itt az eltolás miatt ezt nem tudom alkalmazni.

Jól gondolom, hogy akkor itt lineáris keresés a jó megoldás?


2020. ápr. 19. 14:09
 1/9 anonim ***** válasza:
82%
Esetleg azon érdemes elgondolkozni, hogy bináris kereséssel meg lehetne-e a minimumot vagy a maximumot, szóval az eltolás mértékét keresni. Akkor egy másik bináris kereséssel megvan bármelyik elem.
2020. ápr. 19. 14:34
Hasznos számodra ez a válasz?
 2/9 anonim ***** válasza:
78%
2 binary search, elsővel megkeresed a pivotot, másodikkal az elemet.
2020. ápr. 19. 14:38
Hasznos számodra ez a válasz?
 3/9 A kérdező kommentje:
Valóban, 2 keresésre nem gondoltam, köszi.
2020. ápr. 19. 15:34
 4/9 anonim ***** válasza:
100%

Közben rájöttem, hogy egy binary search is elég, de akkor több a konstans faktor és így nem biztos, hogy összességében gyorsabb. Nem teszteltem.

A 2 körös megoldás mindenesetre egyértelműbb.

2020. ápr. 20. 11:47
Hasznos számodra ez a válasz?
 5/9 A kérdező kommentje:

A két körös az oké, az a logika, amit az egyes válaszoló írt, azt sikerült is implementálni.

De egy körben hogy? :D

2020. ápr. 20. 14:18
 6/9 anonim ***** válasza:
100%

Így valahogy:

https://pastebin pont com/T51DRf6f

2020. ápr. 20. 14:57
Hasznos számodra ez a válasz?
 7/9 A kérdező kommentje:

Mennyire jellemző, hogy ha interjún kapok mondjuk egy ilyen kérdést, akkor hasonló szintű megoldást várnak el?

Mert ha igen, akkor úgy érzem problémáim lesznek az elhelyezkedéssel.

2020. ápr. 20. 19:45
 8/9 anonim ***** válasza:
Nem jellemző, főleg nem junior pozíciónál.
2020. ápr. 20. 20:22
Hasznos számodra ez a válasz?
 9/9 anonim ***** válasza:
Szerintem már a kétkörös keresés ötletével is jobb lennél a juniorok nagyrészénél.
2020. ápr. 20. 20:39
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:

Számítástechnika főkategória kérdései »
Számítástechnika - Programozás kategória kérdései »



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

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!