STL之map(关联式容器)
map是一种关联式容器。由许多对的[key,value]组成,按照特定顺序排列,其键值独一无二,不可重复。在映射中,键值通常用于排序和唯一标识元素,而映射值存储与此键关联的内容,
键和映射值的类型可能不同。map通常实现为二叉搜索树,STL map底层用RB-tree实现。
网易校招笔试:从一篇文章里找出一个单词作为这篇文章的关键词,一个单词可以作为关键词当且仅当它在这篇文章中出现的频率不低于1%,现在他想知道有多少个不同的单词可以作为关键词。一个单词出现的频率=(某一单词出现次数/文章单词总数)*100%
分析题目可知可以以单词作为键,
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<string, int> m;
int num, res = 0;
cin >> num;
for (int i = 0; i < num; i++)
{
string s;
cin >> s;
if (m.count(s) == 1)
m[s] += 1;
else
m[s] = 1;
}
map<string, int>::iterator i = m.begin();
while (i != m.end())
{
if ((i->second*100) >= num)
res++;
i++;
}
cout << res;
return 0;
}
#include <iostream>
#include <map>
using namespace std;
void Print(map<string, int >& m)
{
for (auto it = m.begin(); it != m.end(); it++)
{
pair<string, int> tmp = *it;
cout << tmp.first << " " <<tmp.second<<endl;
}
}
int main()
{
map<string, int> m;
int num, res = 0;
cin >> num;
for (int i = 0; i < num; i++)
{
string s;
cin >> s;
if (m.count(s) == 1) //查询当前元素(键)是否在容器中存在,加入存在 value+1
m[s] += 1;
else
m[s] = 1; //不存在 就将该元素放入容器
}
Print(m); //打印容器元素,可以看到容器中的元素是由某种规则排序的,默认从小到大
map<string, int>::iterator i = m.begin();
while (i != m.end())
{
if ((i->second * 100) >= num)
res++;
i++;
}
cout << res;
return 0;
}