如何在C++ Map中查找具有最大值的Entry
给定C++中的一张地图,任务是找到这张地图中具有最高值的条目。
示例:
输入:Map = { ABC = 10, DEF = 30, XYZ = 20 }
输出:DEF = 30
输入:Map = { 1 = 40, 2 = 30, 3 = 60 }
输出:3 = 60
C++
方法
- 通过迭代器逐个迭代地图条目
map::iterator itr;
for (itr = some_map.begin();
itr != some_map.end();
++itr)
{
//操作
}
C++
- 将第一个条目存储在引用变量中以进行比较。
- 如果当前条目的值大于引用条目的值,则将当前条目存储为引用条目。
- 重复此过程以获取地图中具有最高值的所有条目。
- 最后,引用变量具有地图中具有最高值的所需条目。
- 打印此条目
以下是以上方法的实现:
// C++程序:在Map中查找具有最大值的条目
#include
using namespace std;
//函数:打印Map
void printMap(map sampleMap)
{
map::iterator itr;
for (itr = sampleMap.begin();
itr != sampleMap.end();
++itr) {
cout << itr->first
<< " = " << itr->second << ", ";
}
cout << endl;
}
//函数:查找具有最大值的Entry
pair findEntryWithLargestValue(
map sampleMap)
{
// 引用变量变量,有助于查找具有最高值的Entry
pair entryWithMaxValue
= make_pair(0, 0);
//在Map中进行迭代,以查找所需的条目
map::iterator currentEntry;
for (currentEntry = sampleMap.begin();
currentEntry != sampleMap.end();
++currentEntry) {
//如果这个条目的值比最大值更高,则将这个条目设置为最大值
if (currentEntry->second
> entryWithMaxValue.second) {
entryWithMaxValue
= make_pair(
currentEntry->first,
currentEntry->second);
}
}
return entryWithMaxValue;
}
//驱动程序
int main()
{
// Map
map sampleMap;
sampleMap.insert(pair(1, 40));
sampleMap.insert(pair(2, 30));
sampleMap.insert(pair(3, 60));
//输出Map
cout << "Map: ";
printMap(sampleMap);
//获取具有最大值的条目
pair entryWithMaxValue
= findEntryWithLargestValue(sampleMap);
//打印条目
cout << "Entry with highest value: "
<< entryWithMaxValue.first << " = "
<< entryWithMaxValue.second << endl;
return 0;
}
C++
输出:
Map: 1 = 40, 2 = 30, 3 = 60,
Entry with highest value: 3 = 60
C++
时间复杂度: O(nlogn)
辅助空间: O(n)