Kezdőoldal » Számítástechnika » Programozás » Ez milyen futásidő komplexitás...

Ez milyen futásidő komplexitással számítható ki legjobb esetben?

Figyelt kérdés

Kapok egy string tömböt ahol a stringek számokból és az angol ABC nagybetűiből állhatnak és az a kérdés hogy hány db olyan stringpár van amiben a párok ugyanolyan karakterekből állnak.

Pl {"AA00BB", "5AAB", "AA0B1", "000BA"} tömbnél 1 a megoldás mert egy stringpár (az első és az utolsó string) áll ugyanazokból a karakterekből (A, B, 0). Egy string több párban is szerepelhet, tehát {"A", "AA", "AAA"} tömbnél 3 ilyen pár van.



2021. máj. 23. 10:12
1 2
 1/13 anonim ***** válasza:
Így hirtelen azt mondanám, hogy végigmennék mindegyik stringen, az ismétlődéseket törölném, a maradékot meg eltárolnám egy hashset be(vagy annak megfelelőjébe a nyelvedben), és egy dictionaryben tárolnám hogy hányszor fordult az adott pár. A hashsetet lekérdezni(az ismétlődések miatt), dictionary t módosítani nagyon gyors, az egyetlen lassabb része a stringek feldarabolása(de hacsak nincs egy sok milliárd elemű listád erre sem kell várni).
2021. máj. 23. 11:02
Hasznos számodra ez a válasz?
 2/13 A kérdező kommentje:
Ha törlöm az ismétlődéseket akkor a karakterek sorrendje attól nem feltétlenül fog stimmelni és akkor a hash különböző lesz pl. "AB" és "BA" esetében nem?
2021. máj. 23. 11:09
 3/13 anonim ***** válasza:
Egyszer kell vegig menned minden string minden karakteren, tehat O(c) a legjobb komplexitas, ahol c az osszes karakterek szama a tombben.
2021. máj. 23. 12:09
Hasznos számodra ez a válasz?
 4/13 A kérdező kommentje:
Köszönöm!
2021. máj. 23. 12:21
 5/13 anonim ***** válasza:
0%

string[] words = { "AA00BB","5AAB","000BA","5AB" };

uint[] ORsums = new uint[words.Length];


for (int i = 0; i < words.Length; i++)

{

uint or = 0;

for (int j = 0; j < words[i].Length; j++)

{

char c = words[i][j];

or |= (uint)(c<'A'?1<<(c-'0'+1+'Z'-'A'):1 <<(c - 'A'));

}

ORsums[i] = or;

}


Dictionary<uint, List<int>> pairs = new Dictionary<uint, List<int>>();

for (int i = 0; i < ORsums.Length; i++)

{

if(!pairs.ContainsKey(ORsums[i]))

{

pairs.Add(ORsums[i], new List<int>());

}

pairs[ORsums[i]].Add(i);

}

2021. máj. 23. 13:38
Hasznos számodra ez a válasz?
 6/13 A kérdező kommentje:
#5 ez mi akar lenni?
2021. máj. 23. 13:54
 7/13 anonim ***** válasza:
Félre értette a kérdést gondolom.
2021. máj. 23. 14:10
Hasznos számodra ez a válasz?
 8/13 anonim ***** válasza:

Karatkereket kettő hatványaiként kezelem és összevagyolom, így ha ugyanazokat a karaktereket tartalmazza a szó végösszege is ugyanaz lesz.


Annyit rontottam el a kódban, hogy ulong helyett uintet használtam, így a szám karaktereknél bizonyos esetben túlcsordul az eredmény.

2021. máj. 23. 14:14
Hasznos számodra ez a válasz?
 9/13 A kérdező kommentje:
De az eredmény 1db szám és a te kódod úgy látom nem ad vissza semmit és nem is ír ki semmit.
2021. máj. 23. 14:17
 10/13 anonim ***** válasza:
A végén a szópárokat kigyűjtöttem indexenként egy dictionaryban, innentől már a képzeletre van bízva, hogy mire lehet felhasználni. :)
2021. máj. 23. 14:24
Hasznos számodra ez a válasz?
1 2

Kapcsolódó kérdések:




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!