Ez milyen futásidő komplexitással számítható ki legjobb esetben?
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.
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);
}
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.
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
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!