map的一道题目＜单词识别＞

最近学到了map，为了熟悉使用，找到了一道题目来练练手，题目为牛客网上：KY264 单词识别

做题链接：单词识别_牛客题霸_牛客网 (nowcoder.com)

目录

题目：

要求：

样例：

思路

代码实现

先实现字典序：

实现按次数来的降序

---

题目：

要求：

1. 将一句话中的单词按照出现次数降序排列

2. 相同次数的单词，按照字典序排列（升序排列）

3. 不区分大小写

4. 要求能识别单词和句号

5. 输入的一行为单词和句号，不考虑其他符号

样例：

样例中值得我们注意到的就是：

开头的大写字母 A ，输出的时候是按照小写字母来的

因此我们在输出时以小写为准----大写改小写

思路

1. 将一句话中的大写字母全部换成小写字母

2. 将每个单词插入到map对象中，完成计数+字典序（默认为升序），符合要求

3. 再以次数作为pair类型中的 key 值，单词作为 value 值，插入到 multimap 对象中，完成降序排列

代码实现

#include
#include
#include
using namespace std;
int main()
{
	string str;
	mapint> mp;
	while (getline(cin, str))
	{
		int slow = 0;   //单词的起始下标
		string s;       //存放单个单词
		for (int i = 0; i < str.size(); i++)
		{
			//大写变小写
			if ('A' <= str[i] && str[i] <= 'Z')
			{
				str[i] += 32;
			}
			//取单词放入mp中，插入+计数+自动降序排序
			if (str[i] == ' ' || str[i] == '.')
			{
				int num = i - slow;     //单词大小
				s = str.substr(slow, num);  //通过单词起始下标和大小取出来
				mp[s]++;
				slow = i + 1;  //跳过空格到下一个单词的起始位置
			}
		}
 
		//上述已经按字典序排好了---下面将次数大的放在前面
		//注意次数出现相等，防止去重，要用multimap
		//手动更改为降序
		multimap<int, string, greater<int>> intsort;
		for (const auto& e : mp)
		{
			//插入+排序
			intsort.insert(make_pair(e.second, e.first));
		}
 
		for (const auto& e : intsort)
		{
			cout << e.second << ":" << e.first << endl;
		}
 
	}
	return 0;
}

分析上述如何实现：

先实现字典序：

创建 map 对象 mp，单词作为 pair 类型的 key 值，次数作为 pair 类型的 value 值

输入一句话，while中用 getline 获取字符串，防止直接用 cin 遇到 ‘ ’ 直接停止获取

s 存放单个单词、slow 记录每个单词的起始下标

for 循环下标遍历，将大写字母全部换为小写

遇到 ' ' 或者 ‘ . ’ ，说明前面一定有单词，这时候就可以将单词提取出来：

单词相当于子串，我们用到 substr，num 为单词大小，slow为单词起始下标

通过 i - slow，就可以算出单词大小 

s 存储单词，用 s 将单词插入到 mp 中，并++，计数

最后要更新下一个单词的起始位置， slow = i + 1，跳过空格到下一个单词的起始位置

实现按次数来的降序

这里用到 multimap ，multi 版本允许键值冗余，次数作为 pair 类型的 key 值，单词作为 pair 类型的 value 值

将上述 pair 类型的键值对插入到 multimap 的对象中，完成排序

注意：无论是map还是multimap，默认都是比较 key 值进行升序排列，现在要实现降序，需要手动改变仿函数

multimap<int, string, greater<int>> intsort;

 将 mp 对象的 first 和 second 交换位置，构建 intsort 对象的 pair

for (const auto& e : mp)
{
	//插入+排序
	intsort.insert(make_pair(e.second, e.first));
}

插入完成，排序也就完成，此时 intsort 对象中存储的键值对就是我们需要输出的：

for (const auto& e : intsort)
{
	cout << e.second << ":" << e.first << endl;
}

按照样例的输出要求：单词在前，次数在后，输出整个内容，这个题目就完成了。