Sets und Vektoren. Sind Sets in C ++ schnell? ⇐ C++

[Anonymous]

Bitte lesen Sie die Frage hier - http://www.spoj.com/problems/mrecaman/

Die Frage war, die Recamans -Sequenz des Recaman zu berechnen, wo, a ((a 0) = 0 und a (i) = a (i-1) -i if, a (i-1) -i> 0 und kommt nicht in die Sequenz ein Vor sonst a (i) = a (i-1) + i < /code>. Funktion, die Programmzeiten. Aber wenn ich ein Array und einen Satz benutze, um festzustellen, ob das Element existiert, wird es akzeptiert (sehr schnell). Verwendet Set < /code> schneller?

Code: Select all

vector  sequence;
sequence.push_back(0);
for (int i = 1; i  0 && find(sequence.begin(), sequence.end(), a) == sequence.end())
sequence.push_back(a);
else
sequence.push_back(b);
}
< /code>

 Implementierung < /h2>

festlegenint a[500001]
set  exists;
a[0] = 0;
for (int i = 1; i  0 && exists.find(a[i - 1] - i) == exists.end()) a[i] = a[i - 1] - i;
else a[i] = a[i - 1] + i;
exists.insert(a[i]);
}