Encuentre los elementos K principales con el valor más alto

Dada una lista de elementos y sus valores. La tarea es encontrar los k elementos principales con el valor más alto. Es posible que dos ítems tengan el mismo valor, en ese caso se le dará mayor prioridad al ítem cuyo nombre viene primero (lexicográficamente).

Ejemplos:

Entrada: artículos[] = {Bate, Guantes, Portillos, Pelota}, valores[] = {100, 50, 200, 100}
k = 2

Salida: Wickets Ball
Wickets tiene el valor más alto.
Bat, Ball tiene el mismo valor pero Ball viene primero lexicográficamente.

Enfoque: esta pregunta se puede resolver eligiendo los elementos con avidez de acuerdo con los valores. Ordenaremos la lista de elementos en el orden decreciente de los valores y, en el caso de los mismos valores, los elementos se ordenarán en orden lexicográfico creciente.
Almacenaremos los datos en forma de pares en un vector y usaremos una función de clasificación incorporada con una función de comparación booleana que se usará para comparar dos elementos.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
  
// Boolean Comparator Function
// to compare two pairs of item-value
bool comp(pair<string, int> A, pair<string, int> B)
{
    // Compare the name if the values are equal
    if (A.second == B.second)
        return A.first < B.first;
  
    // Else compare values
    return A.second > B.second;
}
  
// Driver code
int main()
{
    int k = 2;
    int n = 3;
  
    // Store data in a vector of Item-Value Pair
    vector<pair<string, int> > items;
  
    // inserting items-value pairs in the vector
    items.push_back(make_pair("Bat", 100));
    items.push_back(make_pair("Gloves", 50));
    items.push_back(make_pair("Wickets", 200));
    items.push_back(make_pair("Ball", 100));
  
    // Sort items using Inbuilt function
    sort(items.begin(), items.end(), comp);
  
    // Print top k values
    // or if n is less than k
    // Print all n items
    for (int i = 0; i < min(n, k); ++i) {
        cout << items[i].first << '\n';
    }
  
    return 0;
}

Wickets
Ball

Complejidad de tiempo: O (NlogN)

Optimización adicional: podemos optimizar aún más las soluciones anteriores utilizando la estructura de datos del montón . Consulte los k elementos más grandes de una array .