---

🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。
🚁 个人主页：不 良
🔥 系列专栏：🛸C++  🛹Linux
📕 学习格言：博观而约取，厚积而薄发
🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同成长！ 🌹

---

map和set底层结构都是二叉搜索树。

关联式容器

在前面学过的STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。本篇介绍的set和map就是关联式容器。

关联式容器中数据和数据之间有非常强的关联关系，不能随意插入。

键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且英文单词与其中文含义是一一对应的关系，即通过输入单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

template <class T1, class T2>
struct pair
{
	typedef T1 first_type;
	typedef T2 seco_type;
	T1 first;//key
	T2 second;//value
	pair():first(T1()),second(T2()){}//默认构造
	pair(const T1& a, const T2& b):first(a),second(b){}//构造函数
};

在上面的pair类中：

• 是一个模板类，可以存放任意类型的键对值；
• 有两个成员变量：first和second；

一般使用first表示key，second表示value。 键值对要在类外进行访问，所以使用struct定义类而不用class。

make_pair

该函数用来创建pair类型的匿名对象。

根据上面pair类的定义，我们要想创建一个pair类型的匿名对象需要像下面这样写：

pair<string,int>("苹果",1);

上面的方式还需要指定参数类型，所以为了方便，就封装了一个函数模板make_pair，用来快速创建一个匿名对象：

make_pair("苹果",1);

make_pair函数模板的定义如下：

树形结构的关联式容器

根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。 与树形结构容器不同的是，哈希结构容器中的元素是一个无序的序列。

set

认识set

• set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列（默认是升序）；

• set虽然是采用了键值对的方式存储数据，但是在set中，value就是key，即相当于是K模型，并且每个value必须是唯一的，不可以重复，所以可以使用set进行去重；

• 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对，因此在set容器中插入元素时，只需要插入value即可，不需要构造键值对；

• set中的元素不能在容器中修改(元素总是const)，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。但是可以从容器中插入或删除它们；

• 在内部，set中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。当不传入内部比较对象时，set中的元素默认按照小于来比较（默认是升序）；

• set容器通过key访问单个元素的速度通常比unordered_set容器慢，但set容器允许根据顺序对元素进行直接迭代；

• set在底层是用平衡搜索树（红黑树）实现的，所以在set当中查找某个元素的时间复杂度为logN。

set模板参数列表

第一个模板参数T： set中存放元素的类型，实际在底层存储<value, value>的键值对；
Compare（仿函数）：set中元素默认按照小于来比较（默认是升序）；
Alloc：set中元素空间的管理方式，默认使用STL提供的空间配置器管理。

构造函数

构造函数有三个，分别是默认构造函数、使用迭代器区间的构造函数、拷贝构造函数。

下面用代码来使用上面三个构造函数：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
	set<int> s1;//默认构造函数
	vector<int> v = { 66,5,4,11,66,66,77,8,9,22,10,99 };
	set<int> s2(v.begin(), v.end());//迭代器区间构造
	set<int> s3(s2);//拷贝构造
	//打印s1
	for (auto& e : s1)
	{
		cout << e << " ";
	}
	cout << endl;
	//s1内容为空
	//打印s2
	for (auto& e : s2)
	{
		cout << e << " ";
	}
	cout << endl;
	//s2打印出来为4 5 8 9 10 11 22 66 77 99
	
	//打印s3
	for (auto& e : s3)
	{
		cout << e << " ";
	}
	cout << endl;
	//s3打印出来为4 5 8 9 10 11 22 66 77 99
}

运行结果分析：

根据结果我们可以看到set具有排序的功能（默认是升序），而且在数组中相同的元素经放在set容器之后就没有相同的元素了，说明了set具有去重的功能。set具有去重的功能，其底层是二叉搜索树，不能存放相同的元素。

迭代器

set的输出结果是升序的，其底层是二叉搜索树，打印二叉搜索树时使用中序打印出来的就是升序，所以set的迭代器在++时，移动的顺序就是中序遍历的顺序，所以使用迭代器遍历时得到的结果和二叉搜索树中序遍历得到的结果一致。

set迭代器的使用和之前学过的容器一样：

具体使用示范代码：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
	vector<int> v = { 66,5,4,11,66,66,77,8,9,22,10,99 };
	set<int> s1(v.begin(), v.end());//迭代器区间构造
	//正向迭代器的使用
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//反向迭代器的使用
	set<int>::reverse_iterator rit = s1.rbegin();
	while (rit != s1.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

运行结果分析：

插入（insert）

1、插入一个指定值并且返回一个键值对，返回的键值对中迭代器指向新插入的位置。

返回的是pair类型的对象，其中pair的第一个成员是迭代器，其指向的是插入的元素在set中的位置；第二个成员是bool类型，如果成功插入pair类中的第二个成员为true，插入失败pair类中的第二个成员为false。所以这里insert能够做到两个功能：查找和插入（查找成功返回false，查找失败返回true）。

pair<iterator,bool> insert (const value_type& val);

2、在指定的位置插入数据，并且返回插入的位置：

iterator insert (iterator position, const value_type& val);

3、将一段迭代器区间插入到set对象中：

template <class InputIterator>
  void insert (InputIterator first, InputIterator last);

向set中插入一个对象，并且能够保持结构不变，依然符合平衡搜索树。

代码示范：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
	vector<int> v = { 66,5,4,11,66,66,77,8,9,22,10,99 };
	set<int> s1(v.begin(), v.end());//迭代器区间构造
	//正向迭代器的使用
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//构造一个pair类型的对象
	pair<set<int>::iterator, bool> p;
	//接收插入之后的返回值
	p = s1.insert(67);
	it = s1.begin();
	//打印插入的值和是否成功
	cout << *(p.first) << ":" << p.second << endl;

	p = s1.insert(67);
	//打印插入的值和是否成功
	cout << *(p.first) << ":" << p.second << endl;
}

打印结果：

指定位置插入有可能会破环二叉搜索树的结构，所以不建议使用指定位置插入。

删除（erase）

删除指定迭代器位置的值：

void erase (iterator position);

删除指定值并且返回删除指定值的个数（在set容器中没有重复值所以返回值为1，在multiset中才能体现出来）：

size_type erase (const value_type& val);

删除迭代器区间中所有的值（迭代器区间是set的迭代器区间）：

void erase (iterator first, iterator last);

在set中删除一个数据，并且保持结构不变。

查找（find）

iterator find (const value_type& val) const;

查找set中某个元素，如果存在返回所在位置的迭代器，如果不存在，就返回迭代器end()。

代码示范：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
	vector<int> v = { 66,5,4,11,66,66,77,8,9,22,10,99 };
	set<int> s1(v.begin(), v.end());//迭代器区间构造
	//正向迭代器的使用
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	set<int>::iterator it1 = s1.find(66);//存在返回所在值的迭代器位置
	set<int>::iterator it2 = s1.find(666);//不存在返回end()
	if (it1 != s1.end())
		cout << "该值存在" << ":" << *(it1) << endl;
	else
		cout << "该值不存在" << endl;
}

这里和find功能类似的还有一个count函数：

size_type count (const value_type& val) const;

返回指定数据的个数，如果不存在则返回0。

但是由于set具有去重的功能，所以这里的返回值要么是1，要么是0，在set容器中可以用来查找数据是否存在。

获取上下边界

获取下边界（以传入的值为下限，返回一个迭代器）：

iterator lower_bound (const value_type& val) const;

获取上边界（以传入的值为上限，返回一个迭代器）：

iterator upper_bound (const value_type& val) const;

代码示范：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
	vector<int> v = { 66,5,4,11,66,66,77,8,9,22,10,99 };
	set<int> s1(v.begin(), v.end());//迭代器区间构造
	//正向迭代器的使用
	set<int>::iterator it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//输出4 5 8 9 10 11 22 66 77 99
	set<int>::iterator it1 = s1.lower_bound(11);//获取11所在位置的迭代器
	set<int>::iterator it2 = s1.upper_bound(66);//获取66下一个数据的迭代器
	s1.erase(it1, it2);//删除是左闭右开的，获取66下一个位置的迭代器才能将66也删除
	it = s1.begin();
	while (it != s1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	//输出4 5 8 9 10 77 99
}

其他相关操作

函数	函数说明
swap	交换两个set对象
clear	清除set对象中所有数据，但是不删除set对象
empty()	判断set是否为空，如果为空返回true，否则返回flase
size()	返回容器的数据个数，类型为size_t(unsigned int)
max_size()	返回容器中最多能够存放的数据个数

multiset

multiset和set几乎一致，在同一个头文件中，set的功能是排序和去重，而multiset容器仅仅完成排序，容器中允许有相同的数据存在（区别在于multiset支持数据重复，而set不可以）。

在set容器中count函数和erase函数中第二个重载函数（返回被删除个数）没有实际作用，但在multiset中就能够体现它们的作用：

#include <iostream>
#include <set>
#include <vector>
using namespace std;
int main()
{
    vector<int> v = { 66,5,4,11,66,66,9,22,10,4};
    multiset<int> s1(v.begin(), v.end());//迭代器区间构造
    //正向迭代器的使用
    multiset<int>::iterator it = s1.begin();
    while (it != s1.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
    //输出4 4 5 9 10 11 22 66 66 66
    int num1 = s1.count(66);//统计元素66的数据个数
    cout << num1 << endl;//输出3
    int num2 = s1.erase(66);//删除元素66并且返回删除个数
    cout << num2<< endl;//输出3
    it = s1.begin();
    while (it != s1.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;
}

在查找函数find中返回的迭代器位置是查找到的第一个数据的迭代器位置。

map

map是一个关联式容器，底层是二叉搜索树。

map中存放的是键值对，有两个模板参数Key和T，组成键值对。

认识map

• map是关联式容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素；
• 在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair：typedef pair<const key, T> value_type;
• 在内部，map中的元素总是按照键值key进行比较排序的；
• map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)；
• map支持下标访问符，即在[]中放入key，就可以找到与key对应的value；
• map的底层结构为平衡二叉搜索树(红黑树)。

构造函数

默认构造函数创建的map对象为空

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());

插入时可以使用pair创建对象，也可以使用make_pair创建匿名对象：

#include <iostream>
#include <map>
using namespace std;
int main()
{
	map<string, int> fruit;
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
	//插入时可以使用pair创建对象，也可以使用make_pair创建匿名对象
	pair<string, int> p("苹果", 1);
	fruit.insert(p);
    
	fruit.insert(make_pair("香蕉", 1));
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
	return 0;
}

打印结果：

也可以使用迭代器区间进行构造：

template <class InputIterator>
  map (InputIterator first, InputIterator last,
       const key_compare& comp = key_compare(),
       const allocator_type& alloc = allocator_type());

代码示范：

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
	vector<pair<string, int>> v = { {"香蕉",2},{"苹果",3}, {"梨",2}, {"西瓜",6} };
	map<string, int> fruit(v.begin(),v.end());//使用vector迭代器区间进行构造
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
    //进行拷贝构造
    //auto f(fruit);//可以使用自动推导类型
    map<string, int> f(fruit);
	for (auto& e : f)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

打印结果：

注意：

map具有去重的功能，不能插入相同的键值对（不支持重复的数据），同时不能插入key值相同value值不同的键值对。

map的判断逻辑都是只看key值，即first所表示的变量。

插入（insert）

map的插入函数和set的一样，只是map中插入的是键值对。

第一个函数中返回的是一个键值对，返回的键值对pair<iterator,bool>，first是插入键值对所在位置的迭代器，second是bool值，如果插入成功bool值为true，插入失败bool值为false。

迭代器区间插入时，如果map中已经存在key值就不再进行插入。

代码示范：

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
	map<string, int> fruit;//使用默认构造函数
	pair<map<string, int>::iterator, int> ret = fruit.insert(make_pair("黄瓜", 6));//插入一个键值对，返回键值对
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	vector<pair<string, int>> v = { {"香蕉",2},{"苹果",3}, {"梨",2}, {"西瓜",6} };
	fruit.insert(v.begin(), v.end());//插入迭代器区间的数据
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

打印结果：

除了像插入这种增加操作，需要一个键值对，其他操作都是根据键值对中的键值key来处理的。

查找（find）

      iterator find (const key_type& k);
const_iterator find (const key_type& k) const;

根据指定要查找键值对中的键值key去查找，find函数根据key去查找是否存在的。

如果存在，找到以后返回键值对所在位置的迭代器，没有找到返回end迭代器。

代码示范：

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
	map<string, int> fruit;
	vector<pair<string, int>> v = { {"香蕉",2},{"苹果",3}, {"梨",2}, {"西瓜",6} };
	fruit.insert(v.begin(), v.end());
	for (auto& e : fruit)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;
	map<string,int>::iterator ret = fruit.find("香蕉");
	if (ret != fruit.end())
		cout << (*ret).first << ":" << (*ret).second << endl;
		//cout << ret->first << ":" <<  ret->second << endl;
	else
		cout << "找不到" << endl;
}

在上面的代码中cout << (*ret).first << ":" << (*ret).second << endl;输出的时候我们可以先对迭代器解引用再调用first和second，但是平时使用更多的还是->即cout << ret->first << ":" << ret->second << endl;这种方式，这里应该有两个->但是这里省略了一个。

打印结果：

map和set一样，不支持修改，因为可能会破坏二叉搜索树的结构。

operator[]

我们可以使用map统计字符数组中水果出现的次数：

#include <iostream>
//#include <set>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		//通过查找函数，找到返回所在位置的迭代器，没找到返回end迭代器
		map<string, int>::iterator it = countMap.find(e);
		if (it == countMap.end())
		{
			//等于end迭代器时，插入
			countMap.insert(make_pair(e, 1));
		}
		else
		{
			//不等于时second++
			it->second++;
		}
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

打印结果：

但是在map中也可以使用[]，返回的是第二个模板参数，所以上面的代码可以这样写：

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
		"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

operator[]在库中的声明：

可以看到函数参数是键值对中的key值，也就是说key值充当下标。

调用此函数相当于调用：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

总结来说三个步骤：

1、调用insert函数插入键值对；

2、获取insert函数插入成功之后返回的键值对中的first迭代器参数；

3、拿到该迭代器位置键值对中的second，并返回。

对应分解代码如下：

mapped_type& operator[](const key_type& k)
{
	//1、调用insert函数插入键值对
	pair<map<k,mappd_typed()>::iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、获取insert函数插入成功之后返回的键值对中的first迭代器参数；
	map<k,mappd_typed()>::iterator it = ret.first;
	//3、拿到该迭代器位置键值对中的second，并返回
    return (*it).second;
	//return it->second;
}

也可以这样理解：

V& operator[](const K& key)
{
    //1、查找 2、插入
	pair<map<k,V()>::iterator, bool> ret = insert(make_pair(key, V());
    //3、修改
	return ret.first->second;
}

那么countMap[e]++;是如何实现插入、查找、修改的呢？

首先插入e，map中如果不存在e，则boo设置为true，成功插入，此时返回的是插入位置second的引用，引用为0，++之后变成1；如果map中已经存在e，bool值为false，直接返回e位置键值对的second的引用，并且++。

其他相关操作

函数	函数说明
begin和end	获取容器中第一个元素的迭代器和最后一个元素下一个位置的迭代器
rbegin和rend	获取容器中最后一个元素的迭代器和第一个元素前一个位置的迭代器
size	获取容器中元素的个数
empty	判断容器是否为空
clear	清空容器
swap	交换两个容器中的数据
count	获取容器中指定key值的元素个数

multimap

multimap和map都在头文件map中，multimap的使用和map一样（multimap支持相同数据，而map不支持）。

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
	vector<pair<string, int>> v = { {"西瓜",1},{"香蕉" ,2},{"西瓜",2},{"芒果",3} };
	multimap<string, int> countMap;
	for (auto& e : v)
	{
		countMap.insert(e);
	}
	for (auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
}

打印结果：

但是要注意的是multimap中没有重载[]，因为multimap中允许有多个重复键值对，如果重载的话不知道返回哪个。

multimap的inser函数中，没有返回键值对的，返回的是键值对插入之后所在位置的迭代器。

map和set在OJ中的使用

复制带随机指针的链表

题目：复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

• 0 <= n <= 1000
• -10⁴ <= Node.val <= 10⁴
• Node.random 为 null 或指向链表中的节点。

思路：

可以使用map容器让源节点和拷贝结点之间建立kv关系，可以根据map中的kv关系找到random指针指向。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*,Node*> copyNodeMap;
        Node* cur = head;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        //先将链表中的结点都拷贝
        while(cur)
        {
            //创建新结点
            Node* copy = new Node(cur->val);
            //源节点和拷贝结点建立链接关系
            copyNodeMap[cur] = copy;
            if(copytail == nullptr)
            {
                copyhead = copytail = copy;
            }
            else
            {
                copytail->next = copy;
                copytail = copytail->next;
            }
            cur = cur->next;
        }
        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            if(cur->random == nullptr)
                copy->random = nullptr;
            else
            {
                //根据链接关系找到random指针指向
                copy->random = copyNodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

前K个高频单词

题目：前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序排序。

示例1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 "i" 在 "love" 之前。

示例2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，出现次数依次为 4, 3, 2 和 1 次。

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, 不同 words[i] 的数量]

思路一：

可以先使用map将words中的单词统计出现次数，因为要根据出现频率由高到低排序，所以必须要将出现次数设置为key，所以可以将second设置为key，first设置为value放入vector数组中（插入之后不能使用sort对key进行排序，sort是不稳定的排序算法，可以使用库中提供的稳定的排序算法stable_sort，），因为stable_sort函数默认是升序，所以可以实现一个仿函数用来由高到低排序；最后将排完序之后的vector中前k个键值对的second(单词)插入到要返回的vector。

要注意在实现仿函数时，参数是pair类型，注意是first参数的比较还是second参数的比较。

思路一：

可以先使用map将words中的单词统计出现次数，然后将其放入vector数组中，对vector数组进行排序，（sort是不稳定的排序算法，可以使用库中提供的稳定的排序算法stable_sort）因为stable_sort/sort函数默认是升序，所以可以实现一个仿函数用来由高到低排序（要注意在实现仿函数时，参数是pair类型，注意是first参数的比较还是second参数的比较）；最后将排完序之后的vector中前k个键值对中的first参数（字符）尾插到要返回的vector中。

map不能直接使用sort，因为sort底层是一个随机迭代器，而map底层是一个双向迭代器，所以可以先将数据放到vector中再排序。

代码实现：

class Solution {
public:
    //仿函数
    struct Greater{
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2)
        {
            //出现次数大的排前面，当出现次数相同时字母小的排前面
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countwords;
        //统计单词出现次数
        for(auto& e : words)
        {
            countwords[e]++;
        }
        //放入vector数组中
        vector<pair<string,int>> v1(countwords.begin(),countwords.end());
        //排序，放入仿函数
        stable_sort(v1.begin(),v1.end(),Greater());
        //sort(v1.begin(),v1.end(),Greater());
        vector<string> v2;
        //将符合条件的放入vector数组中
        for(int i = 0; i < k; i++)
        {
            v2.push_back(v1[i].first);
        }
        return v2;
    }
};

思路二：

上面的思路我们使用的是sort进行排序，虽然map本身就能排序，但是因为map的本质是排序加去重，所以不能使用，但是可以使用multimap，这里要注意当两个键值相同的时候要如何保证value的顺序，可以通过仿函数来控制。

代码实现：

class Solution {
public:
    //仿函数
    struct Greater{
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const
        {
            //出现次数大的排前面，当出现次数相同时字母小的排前面
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countwords;
        //统计单词出现次数
        for(auto& e : words)
        {
            countwords[e]++;
        }
        //这里使用multiset，这里使用仿函数比较
        multiset<pair<string,int>,Greater> sortset(countwords.begin(),countwords.end());
        vector<string> v2;
        //放入vector数组中
        multiset<pair<string,int>,Greater>::iterator it = sortset.begin();
        //auto it = sortset.begin();
        while(k--)
        {
            v2.push_back(it->first);
            ++it;
        }
        return v2;
    }
};

注意这里的仿函数后面要加上const（避免权限放大问题），不然multiset<pair<string,int>,Greater> sortset(countwords.begin(),countwords.end());这里会报错。

两个数组的交集

题目：两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

思路：

首先就要对已有的两个数组去重，算法库里面有一个去重算法函数unique(必须是有序数组才能去重，可以先sort再去重)；这里可以直接使用set；排好序之后找交集：

代码：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        //去重+排序
        // set<int> s1;
        // set<int> s2;
        // for(auto& e : nums1)
        // {
        //     s1.insert(e);
        // }
        // for(auto& e : nums2)
        // {
        //     s2.insert(e);
        // }

        //也可以直接使用迭代器区间构造
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());
        //set<int>::iterator it1 = s1.begin();
        //set<int>::iterator it2 = s2.begin();
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> v;
        //在s1里面找s2里的数据
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 == *it2)
            {
                v.push_back(*it1);
                ++it1;
                ++it2;
            }
            else if(*it1 < *it2)
            {
                it1++;
            }
            else{
                it2++;
            }
        }
        return v;
    }
};