Dado un mapa en C++ , la tarea es encontrar la entrada en este mapa con el valor más alto. Ejemplos:
Input: Map = {ABC = 10, DEF = 30, XYZ = 20}
Output: DEF = 30
Input: Map = {1 = 40, 2 = 30, 3 = 60}
Output: 3 = 60
Acercarse
- Iterar el mapa entrada por entrada con la ayuda de iteradores
map::iterator itr;
for (itr = some_map.begin();
itr != some_map.end();
++itr)
{
// operations
}
- Almacene la primera entrada en una variable de referencia para comparar inicialmente.
- Si el valor de la entrada actual es mayor que el valor de la entrada de referencia, almacene la entrada actual como la entrada de referencia.
- Repita este proceso para todas las entradas del mapa.
- Al final, la variable de referencia tiene la entrada requerida con el valor más alto en el mapa.
- Imprimir esta entrada
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find the Entry
// with largest Value in a Map
#include <bits/stdc++.h>
using namespace std;
// Function to print the Map
void printMap(map<int, int> sampleMap)
{
map<int, int>::iterator itr;
for (itr = sampleMap.begin();
itr != sampleMap.end();
++itr) {
cout << itr->first
<< " = " << itr->second << ", ";
}
cout << endl;
}
// Function tp find the Entry
// with largest Value in a Map
pair<int, int> findEntryWithLargestValue(
map<int, int> sampleMap)
{
// Reference variable to help find
// the entry with the highest value
pair<int, int> entryWithMaxValue
= make_pair(0, 0);
// Iterate in the map to find the required entry
map<int, int>::iterator currentEntry;
for (currentEntry = sampleMap.begin();
currentEntry != sampleMap.end();
++currentEntry) {
// If this entry's value is more
// than the max value
// Set this entry as the max
if (currentEntry->second
> entryWithMaxValue.second) {
entryWithMaxValue
= make_pair(
currentEntry->first,
currentEntry->second);
}
}
return entryWithMaxValue;
}
// Driver code
int main()
{
// Map
map<int, int> sampleMap;
sampleMap.insert(pair<int, int>(1, 40));
sampleMap.insert(pair<int, int>(2, 30));
sampleMap.insert(pair<int, int>(3, 60));
// Printing map
cout << "Map: ";
printMap(sampleMap);
// Get the entry with largest value
pair<int, int> entryWithMaxValue
= findEntryWithLargestValue(sampleMap);
// Print the entry
cout << "Entry with highest value: "
<< entryWithMaxValue.first << " = "
<< entryWithMaxValue.second << endl;
return 0;
}
Producción:
Map: 1 = 40, 2 = 30, 3 = 60, Entry with highest value: 3 = 60
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)