C++ trae varias estructuras de datos ya implementadas, para simplificarnos la vida :)
std::vector<T> - arreglo dinámicostd::set<T> - conjunto ordenadostd::map<K, V> - diccionario (ordenado por clave)std::stack<T> - pila (LIFO)std::queue<T> - cola (FIFO)std::priority_queue<T> - cola de prioridad (max heap)https://en.cppreference.com/w/cpp/container
Algunas de estas estructuras tienen una interfaz de iteradores, que permite recorrer los elementos de la estructura.
begin(s) - iterador al inicio de una secuencia send(s) - iterador al final de una secuencia s*it - elemento a la derecha del iterador itConceptualmente, un iterador representa una posición en la secuencia.
s = | 2 | 3 | 5 | 8 | 13 | (5 elementos, 6 posiciones)
^ ^
begin(s) end(s)
Notemos que en una secuencia de N elementos, hay N+1 posiciones:
De la misma manera, un iterador corresponde a una posición entre medio de dos elementos consecutivos (o el principio o final de la secuencia)
s = | 2 | 3 | 5 | 8 | 13 |
^
it
entonces *it = 5
Para manipular iteradores, podemos usar los siguientes operadores:
it1 == it2 - apuntan a la misma posicion?++it - avanza a la siguiente posicion--it - retrocede a la posicion anteriorprev(it) - devuelve un iterador a la posicion anteriornext(it) - devuelve un iterador a la posicion siguientePor ejemplo, podemos recorrer la secuencia s e imprimir cada elemento usando un bucle for.
for (auto it = begin(s); it != end(s); ++it) {
cout << *it << " ";
}
cout << "\n";
https://en.cppreference.com/w/cpp/iterator
Charla “C++ seasoning” de Sean Parent: https://www.youtube.com/watch?v=W2tWOdzgXHA
Nos dan un arreglo de N numeros distintos
a[1],a[2], …,a[N]. Encontrar la minima diferencia entre dos elementos de este arreglo.Restricciones:
1 <= N <= 5*10^51 <= a[i] <= 10^9Entrada:
La primera linea contiene el entero N
La siguiente linea tiene N numeros distintos
a[1],a[2], …,a[N].Salida:
La minima diferencia entre dos elementos de
a.Ejemplo
6 9000 5004 1000 8900 5001 11003
int a[500100];
int main() {
int n;
cin >> n;
forn(i, n) {
cin >> a[i];
}
int ans = abs(a[1] - a[0]);
forn(i, n) {
forn(j, n) {
if (i != j) {
ans = min(ans, abs(a[i] - a[j]));
}
}
}
cout << ans << endl;
return 0;
}
Para mejorar la solucion naive, podemos usar std::vector, que es un arreglo dinámico.
vector<T>(n) - crea un vector de n elementos de tipo Ta[i] - elemento en la posicion i del vectorvector<T>(begin(s), end(s)) - crea un vector con los elementos de la secuencia sa.size() - tamaño del vectora.push_back(x) - agrega el elemento x al final del vectora.pop_back() - elimina el último elemento del vectora.back() - último elemento del vectora.clear() - elimina todos los elementos del vectora.empty() - verifica si el vector está vacíobegin(a) - iterador al inicio del vectorend(a) - iterador al final del vectorhttps://en.cppreference.com/w/cpp/container/vector
Usando un vector, podemos leer la entrada de la siguiente manera, sin necesidad de escribir el maximo N.
vector<int> a(n);
forn(i, n) {
cin >> a[i];
}
El resto del codigo es el mismo.
El codigo anterior prueba cada par de elementos dos veces, una vez como (i, j) y otra como (j, i). Podemos hacer esta comparación solo una vez.
int ans = abs(a[1] - a[0]);
forn(i, n) {
forn(j, i) {
ans = min(ans, abs(a[i] - a[j]);
}
}
Esto es el doble de rapido, pero no cambia el costo asintotico, sigue siendo O(N^2).
int N;
cin >> N;
vector<int> a(n);
forn(i, n) {
cin >> a[i];
}
int ans = abs(a[1] - a[0]);
forn(i, n) {
forn(j, n) {
if (i != j) {
ans = min(ans, abs(a[i] - a[j]);
}
}
}
// O(N^2)
int ans = abs(a[1] - a[0]);
set<int> s;
for (int x : a) { // O(N) iteraciones
if (auto it = s.upper_bound(x); it != end(s)) { // O(log N)
ans = min(ans, *it - x); // O(1)
}
if (auto it = s.lower_bound(x); it != begin(s)) { // O(log N)
ans = min(ans, x - *prev(it)); // O(1)
}
}
// total: O(N log N)
Simplificar
int ans = abs(a[1] - a[0]);
set<int> s(begin(a), end(a)); // O(1)
for (int x : a) { // O(N) iteraciones
if (auto it = s.upper_bound(x); it != end(s)) { // O(log N)
ans = min(ans, *it - x);
}
}
// total: O(N log N)
<algorithm>C++ trae tambien una biblioteca de algoritmos. Entre otros, tiene:
sort(begin(a), end(a)) - ordena el vector areverse(begin(a), end(a)) - invierte el vector arotate(begin(a), begin(a) + k, end(a)) - rota el vector a k posiciones a la derechaunique(begin(a), end(a)) - elimina los elementos duplicados del vector afill(begin(a), end(a), x) - llena el vector a con el valor xhttps://en.cppreference.com/w/cpp/algorithm
int ans = a[1] - a[0];
sort(begin(a), end(a)); // O(N log N)
forn(i, n-1) ans = min(ans, a[i+1] - a[i]); // O(N)
// total: O(N log N)