Het is zelfs heel belangrijk dat uw waarden tussen 1 en 100 liggen! Omdat je met een vector van 1.000.000 veel getallen hebt die gelijk zijn en je ze niet allemaal hoeft te inspecteren! Wat je kunt doen is het volgende:
Opmerking: de volgende code is slechts een overzicht! Het kan onvoldoende foutcontrole bevatten en is hier alleen om u het idee te geven, niet voor copy paste!
Opmerking 2: Toen ik het antwoord schreef, nam ik aan dat de getallen binnen het bereik [0, 99] lagen. Toen las ik dat ze daadwerkelijk in [1, 100] zijn. Dit is duidelijk geen probleem en je kunt ofwel -1 alle cijfers of zelfs beter, alle 100s naar 101s veranderen.
bool exists[100] = {0}; //exists[i] means whether i exists in your vector
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
exists[vect[i]] = true;
Dan doe je hetzelfde als wat je eerder deed:
for(unsigned int x = 0; x < 98; x++)
if (exists[x])
for(unsigned int y = x+1; y < 99; y++)
if (exists[y])
for(unsigned int z = y+1; z < 100; z++)
if (exists[z])
{
//{x, y, z} is an answer
}
Een ander ding dat je kunt doen is meer tijd besteden aan voorbereiding om minder tijd te hebben om de paren te genereren. Bijvoorbeeld:
int nums[100]; //from 0 to count are the numbers you have
int count = 0;
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
bool exists = false;
for (int j = 0; j < count; ++j)
if (vect[i] == nums[j])
{
exists = true;
break;
}
if (!exists)
nums[count++] = vect[i];
}
Dan
for(unsigned int x = 0; x < count-2; x++)
for(unsigned int y = x+1; y < count-1; y++)
for(unsigned int z = y+1; z < count; z++)
{
//{nums[x], nums[y], nums[z]} is an answer
}
Laten we 100 beschouwen als een variabele, dus laten we het k
noemen, en de werkelijke aantallen die in de array aanwezig zijn als m
(die kleiner is dan of gelijk is aan k
).
Met de eerste methode hebt u O (n)
voorbereiding en O (m ^ 2 * k)
handelingen om te zoeken naar de waarde die vrij snel is.
In de tweede methode hebt u O (nm)
voorbereiding en O (m ^ 3)
voor het genereren van de waarden. Gegeven uw waarden voor n
en m
duurt de voorbereiding te lang.
Je zou eigenlijk de twee methoden kunnen samenvoegen om het beste van beide werelden te krijgen, dus zoiets als dit:
int nums[100]; //from 0 to count are the numbers you have
int count = 0;
bool exists[100] = {0}; //exists[i] means whether i exists in your vector
for (unsigned int i = 0, size = vect.size(); i < size; ++i)
{
if (!exists[vect[i]])
nums[count++] = vect[i];
exists[vect[i]] = true;
}
Dan:
for(unsigned int x = 0; x < count-2; x++)
for(unsigned int y = x+1; y < count-1; y++)
for(unsigned int z = y+1; z < count; z++)
{
//{nums[x], nums[y], nums[z]} is an answer
}
Deze methode heeft O (n)
voorbereiding en O (m ^ 3)
kosten om de unieke tripletten te vinden.
Edit: It turned out that for the OP, the same number in different locations are considered different values. If that is really the case, Dan I'm sorry, there is no faster solution. The reason is that all the possible combinations themselves are C(n, m)
(That's a combination) that although you are generating each one of them in O(1)
, it is still too big for you.