Dada una array de enteros, encuentre el elemento mínimo (o máximo) y el elemento mayor (o menor) que eso en menos de 2n comparaciones. La array dada no está necesariamente ordenada. Se permite espacio adicional.
Ejemplos:
Input: {3, 6, 100, 9, 10, 12, 7, -1, 10}
Output: Minimum: -1, Second minimum: 3
Ya hemos discutido un enfoque en la publicación a continuación.
Encuentre el elemento más pequeño y el segundo más pequeño en una array
Las comparaciones de los elementos de la array pueden ser costosas si los elementos de la array son de gran tamaño, por ejemplo, strings grandes. Podemos minimizar el número de comparaciones utilizadas en el enfoque anterior.
La idea se basa en el árbol del torneo . Considere cada elemento de la array dada como un Node hoja.
Primero, encontramos el elemento mínimo como se explica al construir un tee de torneo. Para construir el árbol, comparamos todos los pares de elementos adyacentes (Nodes de hoja) entre sí. Ahora tenemos n/2 elementos que son más pequeños que sus contrapartes (de cada par, el elemento más pequeño forma el nivel superior al de las hojas). Nuevamente, encuentra los elementos más pequeños en cada uno de los n/4 pares. Continúe este proceso hasta que se cree la raíz del árbol. La raíz es el mínimo.
A continuación, recorremos el árbol y, mientras lo hacemos, descartamos los subárboles cuya raíz es mayor que el elemento más pequeño. Antes de descartar, actualizamos el segundo elemento más pequeño, que contendrá nuestro resultado. El punto a entender aquí es que el árbol está equilibrado en altura y tenemos que gastar solo tiempo de registro para recorrer todos los elementos que alguna vez se compararon con el mínimo en el paso 1. Por lo tanto, la complejidad de tiempo general es n + registro . El espacio auxiliar necesario es O(2n), ya que el número de Nodes hoja será aproximadamente igual al número de Nodes internos.
// C++ program to find minimum and second minimum
// using minimum number of comparisons
#include <bits/stdc++.h>
using namespace std;
// Tournament Tree node
struct Node
{
int idx;
Node *left, *right;
};
// Utility function to create a tournament tree node
Node *createNode(int idx)
{
Node *t = new Node;
t->left = t->right = NULL;
t->idx = idx;
return t;
}
// This function traverses tree across height to
// find second smallest element in tournament tree.
// Note that root is smallest element of tournament
// tree.
void traverseHeight(Node *root, int arr[], int &res)
{
// Base case
if (root == NULL || (root->left == NULL &&
root->right == NULL))
return;
// If left child is smaller than current result,
// update result and recur for left subarray.
if (res > arr[root->left->idx] &&
root->left->idx != root->idx)
{
res = arr[root->left->idx];
traverseHeight(root->right, arr, res);
}
// If right child is smaller than current result,
// update result and recur for left subarray.
else if (res > arr[root->right->idx] &&
root->right->idx != root->idx)
{
res = arr[root->right->idx];
traverseHeight(root->left, arr, res);
}
}
// Prints minimum and second minimum in arr[0..n-1]
void findSecondMin(int arr[], int n)
{
// Create a list to store nodes of current
// level
list<Node *> li;
Node *root = NULL;
for (int i = 0; i < n; i += 2)
{
Node *t1 = createNode(i);
Node *t2 = NULL;
if (i + 1 < n)
{
// Make a node for next element
t2 = createNode(i + 1);
// Make smaller of two as root
root = (arr[i] < arr[i + 1])? createNode(i) :
createNode(i + 1);
// Make two nodes as children of smaller
root->left = t1;
root->right = t2;
// Add root
li.push_back(root);
}
else
li.push_back(t1);
}
int lsize = li.size();
// Construct the complete tournament tree from above
// prepared list of winners in first round.
while (lsize != 1)
{
// Find index of last pair
int last = (lsize & 1)? (lsize - 2) : (lsize - 1);
// Process current list items in pair
for (int i = 0; i < last; i += 2)
{
// Extract two nodes from list, make a new
// node for winner of two
Node *f1 = li.front();
li.pop_front();
Node *f2 = li.front();
li.pop_front();
root = (arr[f1->idx] < arr[f2->idx])?
createNode(f1->idx) : createNode(f2->idx);
// Make winner as parent of two
root->left = f1;
root->right = f2;
// Add winner to list of next level
li.push_back(root);
}
if (lsize & 1)
{
li.push_back(li.front());
li.pop_front();
}
lsize = li.size();
}
// Traverse tree from root to find second minimum
// Note that minimum is already known and root of
// tournament tree.
int res = INT_MAX;
traverseHeight(root, arr, res);
cout << "Minimum: " << arr[root->idx]
<< ", Second minimum: " << res << endl;
}
// Driver code
int main()
{
int arr[] = {61, 6, 100, 9, 10, 12, 17};
int n = sizeof(arr)/sizeof(arr[0]);
findSecondMin(arr, n);
return 0;
}
Producción:
Minimum: 6, Second minimum: 9
Podemos optimizar el código anterior evitando la creación de Nodes de hoja, ya que esa información se almacena en la array (y sabemos que los elementos se compararon en pares).
Este artículo es una contribución de Dhruv . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA