Programa C++ para encontrar k elementos máximos de array en el orden original

Dada una array arr[] y un entero k, necesitamos imprimir k elementos máximos de la array dada. Los elementos deben imprimirse en el orden de la entrada.
Nota: k siempre es menor o igual que n.

Ejemplos:  

Input : arr[] = {10 50 30 60 15}
        k = 2
Output : 50 60
The top 2 elements are printed
as per their appearance in original
array.

Input : arr[] = {50 8 45 12 25 40 84}
            k = 3
Output : 50 45 84

Método 1: Buscamos el elemento máximo k veces en la array dada. Cada vez que encontramos un elemento máximo, lo imprimimos y lo reemplazamos con menos infinito (INT_MIN en C) en la array. La complejidad temporal de este método es O(n*k).

// C++ program to find k Maximum elements
#include <bits/stdc++.h>
using namespace std;
 
// Function to print k Maximum elements
void printMax(int a[], int n, int k)
{
    int b[n],c[n];
     
    // Coping the array a
    // into c and initialising
    // elements in array b as 0.
    for(int i=0;i<n;i++)
    {
        c[i]=a[i];
        b[i]=0;
    }
     
    // Iterating for K-times
    // to find k-maximum
    for(int i=0;i<k;i++)
    {
        // finding the maximum element
        // and its index
        int maxi=INT_MIN;
        int index;
        for(int j=0;j<n;j++)
        {
            if(a[j]>maxi)
            {
                maxi=a[j];
                index=j;
            }
        }
        // Assigning 1 in order
        // to mark the position
        // of all k maximum numbers
        b[index]=1;
        a[index]=INT_MIN;
    }
     
    for(int i=0;i<n;i++)
    {
        // Printing the k maximum
        // elements of the array
        if(b[i]==1)
        cout<<c[i]<<" ";
    }
}
 
// Driver code
int main()
{
    int a[] = { 50, 8, 45, 12, 25, 40, 84 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3;
    printMax(a, n, k);
    return 0;
}
 
// This code is contributed by Aman kumar.

50 45 84 

Complejidad temporal: O(n*k)
Espacio auxiliar: O(n)

Método 2: en este método, almacenamos la array original en una nueva array y ordenaremos la nueva array en orden descendente. Después de ordenar, iteramos la array original de 0 a n e imprimimos todos los elementos que aparecen en los primeros k elementos de la nueva array. Para buscar, podemos hacer Búsqueda binaria .

// C++ program to find k maximum elements
// of array in original order
#include <bits/stdc++.h>
using namespace std;
 
// Function to print m Maximum elements
void printMax(int arr[], int k, int n)
{
    // vector to store the copy of the
    // original array
    vector<int> brr(arr, arr + n);
 
    // Sorting the vector in descending
    // order. Please refer below link for
    // details
    // https://www.geeksforgeeks.org/sort-c-stl/
    sort(brr.begin(), brr.end(), greater<int>());
 
    // Traversing through original array and
    // printing all those elements that are
    // in first k of sorted vector.
    // Please refer https://goo.gl/44Rwgt
    // for details of binary_search()
    for (int i = 0; i < n; ++i)
        if (binary_search(brr.begin(),
                 brr.begin() + k, arr[i],
                        greater<int>()))
            cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 50, 8, 45, 12, 25, 40, 84 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    printMax(arr, k, n);
    return 0;
}

Producción: 

50 45 84 

Complejidad de tiempo: O(n Log n) para ordenar. 
Espacio Auxiliar: O(n)
 

¡ Consulte el artículo completo sobre Encontrar k elementos máximos de array en el orden original para obtener más detalles!