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 » Elakadtam egy HackerRanks...

Elakadtam egy HackerRanks feladatban, hol lehet a hibám? (bármely C szerű nyelvben)

Figyelt kérdés

HackerRanks, Picking numbers feladat. Nem konkrét interjúra vagy ilyesmire kell és nem iskolai feladat, az oldal email-ben küldte.


Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1.


....


Sample Input 0


6 a hossza

4 6 5 3 3 1 a számok, nem feltétlenül rendezett, mint a mellékelt ábra is mutatja


Sample Output 0


3



https://pastebin (pont) com/ZAHk1W0F


Hol a hibám?

Ez C#, de nem muszáj ahhoz ragaszkodni, bármely C nyelvben megérteném a lényeget. :)


2020. jan. 28. 15:13
❮ 1 2 3 4
 31/37 anonim ***** válasza:
54%

HashMap-ben (illetve nekünk inkább dictionary a releváns) a worst case keresés és beszúrás O(n) idejű.


Az oké, hogy átlagosan sokkal gyorsabb...

2020. jan. 28. 21:33
Hasznos számodra ez a válasz?
 32/37 anonim ***** válasza:
100%

Ez így van. És most gondold át, hogy számok esetében mikor lesz ütközés.

Csak akkor, ha a szám nem fér bele a hashbe.

Ezt ellenőrizni O(1)-es művelet és ez esetben másik HashMap-be rakjuk, ilyen egyszerű.

2020. jan. 28. 21:40
Hasznos számodra ez a válasz?
 33/37 anonim ***** válasza:
51%

Igen, és ugyanott vagyunk ahonnan kiindultunk... exponenciális méretű memóriára van szükség.

Nyilván a 1-99-cel nincs gond, ott jó az int[99] is...

2020. jan. 28. 21:46
Hasznos számodra ez a válasz?
 34/37 anonim ***** válasza:
27%
Miért lenne szükség exponenciális méretű memóriára? :)
2020. jan. 28. 21:47
Hasznos számodra ez a válasz?
 35/37 anonim ***** válasza:
51%

Memória=tárhely=space, értsd ahogy szeretnéd.. nyilván nem fontos hogy RAM legyen. Azért, hogy biztosan elkerüld az ütközéseket. Csak gondolj bele.

NYilván attól függ, hogy mennyi tárhely kell, hogy legrosszabb esetben mennyi ütközés elfogadott. Ha O(log n)-es hashmeter szeretnél, akkor nem kell exponenciális....de akkor nem lesz az algoritmusod lineáris.


(Egyébként lehet létezik lineáris algoritmus, most csak a map-es megoldásról beszéltem)

2020. jan. 28. 21:51
Hasznos számodra ez a válasz?
 36/37 anonim ***** válasza:
65%
De mit nem értesz azon, hogy nincs ütközés? Egy sem. Semennyi. Mivel számokról van szó (és nem stringekről pl.), így 100% biztosan számítható, hogy mikor lenne ütközés és O(1)-ben elkerülhető.
2020. jan. 28. 21:55
Hasznos számodra ez a válasz?
 37/37 anonim ***** válasza:
64%
36-os hagyd rá, mintha falnak beszélnél.
2020. jan. 28. 21:57
Hasznos számodra ez a válasz?
❮ 1 2 3 4

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!