Ú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.

• #12158 #57018880 törölt tag Chesterfield #12154

  Új Válasz 2018-07-14 08:09:47 #12158

  Ú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

  

  #57018880

  törölt tag

  válasz Chesterfield #12154 üzenetére

  Szerintem az alap probléma az volt, hogy a listát minden iterációban újra számoltatod a hossza meg nem változik.

• #12156 dabadab titán Chesterfield #12154

  Új Válasz 2018-07-13 21:53:53 #12156

  Ú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

  

  dabadab

  titán

  válasz Chesterfield #12154 üzenetére

  i-t elég lenne csak count-1-ig elvinni, de mást nem látok benne.

  Ja, közben megnézem Sspot linkjét, az tényleg jó:

  Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < list.length; i++) {
int needed = sum - list[i];
if (indexMap.get(needed) != null) {
return new int[]{i, indexMap.get(needed)};
}

• #12155 #81999360 törölt tag Chesterfield #12154

  Új Válasz 2018-07-13 21:47:32 #12155

  Ú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

  

  #81999360

  törölt tag

  válasz Chesterfield #12154 üzenetére

  Ezek?

  Szerk: Már látom, hogy ez nem pont az a feladat, de talán a stackoverflow jó hely elindulni.

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