Új hozzászólás Aktív témák

• BaLinux tag

  #344

  #343 Miracle

  2005-07-02 01:10:16

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  BaLinux

  tag

  #343 Miracle

  #343 Miracle

  eheh hat ez sztem nem tul optimalis megoldas ;)
  ime az en otletem:
  olvasod az egyik filet, es pakolod bele az elemeket gondolkodas nelkul 1 hashtable-be.
  aztan amikor vegeztel elkezded olvasni a masik filet, es minden szora rakeresel a hashtable-ben, ha megtalalod akkor kiirod kimenetre, (es ha csak egyszer kell kiirni akkor torlod a hashtable-bol, ha tobbszor is lehet akkor ez a zarojel targytalan) es olvasol tovabb
  ez kb 6 sor amit en most felvazoltam, es szerintem gyorsabb is, es kevesebb memo kell hozza, mint a ket vektoros megoldashoz
  
  szerk: hashtable helyett valamilyen set-szeru dologba megjobb volna, foleg ha hash-alapu, de nem tudom van-e ilyen adatszerkerkezet alapbol az APIban
  
  [Szerkesztve]

  Gondoltam a HashSet-re, de elvetettem, mert az kezdőknek esetleg kevésbé érthető hogy mért jó az.
  Amire gondoltál az a HashSet, ilyen van, rendben. Elvileg a beillesztés/keresés O(1) idejű benne, de pl. telítettség függvénye a konstans szorzó és alapvetően elég nehéz megjósolni. Összességében tehát O(n+m) lépés lenne a HashSetes módszer. A rendezéses módszer garantált O(nlogn)+O(mlogm), meg még min(n,m) lépés.
  Attól függ hogy átlagban, vagy legrosszabb esetben hogyan kell teljesítenie az algoritmusnak.

Új hozzászólás Aktív témák