Estructura de datos basada en políticas de conjuntos ordenados integrada
Conjunto ordenado es una estructura de datos basada en políticas en g ++ que mantiene elementos únicos en orden ordenado. Realiza todas las operaciones realizadas por Set en STL en complejidad O (logN) .
Además de eso, las siguientes dos operaciones también se realizan en complejidad O (logN) :
- order_of_key (K): Número de elementos estrictamente menores que K .
- find_by_order(k): K -ésimo elemento en un Conjunto (contando desde cero).
La función find_by_order() acepta una clave, digamos K , como argumento y devuelve el iterador al K -ésimo elemento más grande del Conjunto.
Ejemplos:
Nota: si K >= N , donde N es el tamaño del conjunto, la función devuelve 0 o, en algunos compiladores, el iterador al elemento más pequeño.
A continuación se muestra la implementación de la función find_by_order() en C++:
C++14
// C++ program to implement find_by_order()
// for Policy Based Data Structures
#include <bits/stdc++.h>
// Importing header files
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
// Declaring Ordered Set
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
pbds;
// Driver Code
int main()
{
int arr[] = {1, 5, 6, 17, 88};
int n = sizeof(arr)/sizeof(arr[0]);
pbds S;
// Traverse the array
for (int i = 0; i < n; i++) {
// Insert array elements
// into the ordered set
S.insert(arr[i]);
}
// Returns iterator to 0-th
// largest element in the set
cout << *S.find_by_order(0) << " ";
// Returns iterator to 2-nd
// largest element in the set
cout << *S.find_by_order(2);
return 0;
}
1 6
Complejidad de tiempo: O(n*log(n))
Espacio auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por p1173mayank y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA