Elemento K’th más pequeño/más grande usando STL

Dada una array y un número k donde k es más pequeño que el tamaño de la array, necesitamos encontrar el k-ésimo elemento más pequeño en la array dada. Ejemplos:

Input : arr[] = {7, 10, 4, 3, 20, 15}
            k = 2
Output : 4
Smallest element is 3. Second smallest
is 4.

Input : arr[] = {7, 10, 4, 3, 3, 15}
            k = 2
Output : 4
Even if there are more than one occurrences
of 3, answer should be 4.

Input :arr[] = {7, 10, 4, 3, 20, 15}
          k = 4
Output : 10

Usamos set en C++ STL . 1) Insertar todos los elementos en un conjunto. 2) Atraviese el conjunto e imprima el k-ésimo elemento. 

Implementación:

// STL based C++ program to find k-th smallest
// element.
#include <bits/stdc++.h>
using namespace std;
 
int kthSmallest(int arr[], int n, int k)
{
 // Insert all elements into the set
 set<int> s;
 for (int i = 0; i < n; i++)
  s.insert(arr[i]);
 
 // Traverse set and print k-th element
 auto it = s.begin();
 for (int i = 0; i < k - 1; i++)
  it++;
 return *it;
}
 
int main()
{
 int arr[] = { 12, 3, 5, 7, 3, 19 };
 int n = sizeof(arr) / sizeof(arr[0]), k = 2;
 cout << "K'th smallest element is "
  << kthSmallest(arr, n, k);
 return 0;
}

K'th smallest element is 5

Complejidad de tiempo: O(n Log n) . Tenga en cuenta que establecer en STL utiliza un BST de autoequilibrio internamente y, por lo tanto, la complejidad de tiempo de las operaciones de búsqueda e inserción es O (log n). 
Espacio auxiliar: O(n) donde n es el tamaño de la array

Publicaciones relacionadas: 
K’th elemento más pequeño/más grande en array sin clasificar | Establecer 1
k’ésimo elemento más pequeño/más grande en array sin clasificar | Conjunto 2 (Tiempo lineal esperado K’th elemento más pequeño/más grande en array no ordenada | Conjunto 3 (Tiempo lineal en el peor de los casos)

Este artículo es una contribución de Roshan Halwai . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.