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

• #12159 kovisoft őstag Chesterfield #12154

  Új Válasz 2018-07-14 10:46:32 #12159

  Ú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

  Privát üzenet küldése

  

  kovisoft

  őstag

  válasz Chesterfield #12154 üzenetére

  Amit írtál, az ugye N*N-es algoritmus, de meg lehet csinálni N*log(N) lépésben is:

  (1) Lerendezed a listát úgy, hogy eltárolod az elemek eredeti indexeit is. Ez O(N*log(N)) lépés.

  (2) Végigmész a rendezett listán a két végéről indulva, az első elemhez a végéről megkeresed azt, amivel az összegük már a keresett összeg alá esik, ekkor az alsóval lépkedsz felfelé, amíg az összegük túlnő a keresett összegen, aztán megint fentről lefelé, és így tovább. Ha bármikor megtaláltad a keresett összeget, akkor visszaadod az indexeket, különben null. Ez O(N) lépés.

  Szerk: akkor ér véget az algoritmus, amikor a két végéről indulva összeérnek az elemek.

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