C++标准模板库 -- map和set

序列式容器和关联式容器

        在本篇文章之前，我们已经接触了STL中的部分容器：如string、vector、list、deque、array、forward_list等，这些容器被统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值一般没有紧密的关联关系，比如将随机元素交换后该容器依旧为序列式容器。该容器的顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

        关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个元素间的位置有紧密的关联关系，交换一下，它的存储结构就被破坏了。关联式容器有 map/set 系列和 unordered_map/unordered_set 系列。该容器的顺序容器中的元素是按关键字来保存和访问的。在本篇文章中我们讲解的是 map 和 set，两个容器的底层是红黑树结构，红黑树是一颗平衡二叉搜索树（一种特殊的二叉搜索树）。set是key搜索场景的结构，map是ket_value搜索场景的结构。

set系列容器

set和multiset

参考文档： <set> 介绍- C++ 官方文档。

set类的介绍

template <  class T,                      // set::key_type/value_typeclass Compare = less<T>,      // set::key_compare/value_compareclass Alloc = allocator<T>    // set::allocator_type> class set;
  • set 声明如上，T就是 set 底层关键字 key 的类型。
  • set 默认要求 T 支持小于比较（Less<T>），如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模板参数。
  • set 底层存储数据的内存是从空间配置器申请的，如果有需要可以实现自己的内存池，传给第三个参数。
  • 但一般情况下，我们都不需要传后两个模板参数。
  • set 底层使用红黑树实现的，增删查的效率是O(LogN)，迭代器遍历是走的二叉搜索树的中序遍历，所以遍历是有序的。

set类的函数接口

        在前面我们已经学习了 vector/llist 等容器的使用，STL 容器结构设计都高度相似，因此我们不会将所有接口都介绍一遍，而是通过文档介绍一些独有和比较重要的接口。

构造函数和迭代器

        set 支持正向和反向迭代遍历，遍历默认按升序，因为底层是二叉搜索树，迭代器走的是中序遍历；支持迭代器就意味着支持范围 for，set 的 iterator 和 const_iterator 都不支持迭代器修改数据（key值），这样会破坏底层二叉搜索树的结构。

// empty (1) 无参默认构造
explicit set(const key_compare& comp = key_comeare(),const allocator_type& alloc = allocator_type());
// range  (2) 迭代器区间构造
template<class InputIterator>set(InputIterator first, InputIterator last,const key_compare& comp = key_comeare(),const allocator_type& alloc = allocator_type());
// copy  (3) 拷贝构造set(const set& x);// initializer list  (4) initializer 列表初始化构造set(initializer_list<value_type> il,const key_compare& comp = key_comeare(),const allocator_type& alloc = allocator_type());// 迭代器是一个双向迭代器
//iterator -> a bidirectional iterator to const value_type//正向迭代器
iterator begin();
iterator end();//反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

增删查

//Member types  成员类型说明
//key_type	 ->		The first template parameter(T)
//value_type	 ->		The first template parameter(T)//单个数据插入，如果已经存在则插入失败。
pair<iterator, bool> insert(const value_type& val);
//列表插入，本质是将所有元素依次insert，已经在容器中存在的值不会重复插入。
void insert(initializer_list<value_type> il);
//迭代器区间插入，已经在容器中存在的值不会插入
template<class InputIterator>
void insert(InputIterator first, InputIterator last);//查找val，返回val所在的节点的迭代器，没有找到就返回end();
iterator find(const value_type& val);
//查找val，返回val的个数
size_type count(const value_type& val) const;
//删除一个迭代器位置的值
iterator erase(const_iterator position);
//删除val，val不存在返回0，存在返回1。
size_type erase(const value_type& val);
//删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);//返回大于等于val值位置的迭代器
iterator lower_bound(const value_type& val) const;
//返回大于val值位置的迭代器
iterator upper_bound(const value_type& val) const;

set接口的使用

insert与迭代器遍历

#include<iostream>
#include<set>
using namespace std;
int main()
{// 去重+升序排序set<int> s;// 去重+降序排序（给⼀个⼤于的仿函数）//set<int, greater<int>> s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//set<int>::iterator it = s.begin();auto it = s.begin();while (it != s.end()){// error C3892: “it”: 不能给常量赋值// 不能修改key值// *it = 1;cout << *it << " ";++it;} cout << endl;// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败s.insert({ 2,8,3,9 });for (auto e : s){cout << e << " ";} cout << endl;set<string> strset = { "sort", "insert", "add" };// 遍历string⽐较ascll码⼤小顺序遍历的for (auto& e : strset){cout << e << " ";} cout << endl;
}

count、find 和 erase

#include<iostream>
#include<set>
using namespace std;
int main()
{set<int> s = { 4,2,7,2,8,5,9 };for (auto e : s){cout << e << " ";} cout << endl;// 删除最⼩值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;// 直接删除xint x;cin >> x;int num = s.erase(x);if (num == 0){cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";} cout << endl;// 直接查找在利⽤迭代器删除xcin >> x;auto pos = s.find(x);if (pos != s.end()){s.erase(pos);} else{cout << x << "不存在！" << endl;} for (auto e : s){cout << e << " ";} cout << endl;// 算法库的查找 O(N)auto pos1 = find(s.begin(), s.end(), x);// set⾃⾝实现的查找 O(logN)auto pos2 = s.find(x);// 利⽤count间接实现快速查找cin >> x;//s.count(x)   计算 x 在 s 中的个数，因为set中不会有重复值，所以只会有0和1两种结果if (s.count(x))    {cout << x << "在！" << endl;} else{cout << x << "不存在！" << endl;} return 0;
}
#include<iostream>
#include<set>
using namespace std;
int main()
{std::set<int> myset;for (int i = 1; i < 10; i++)myset.insert(i * 10);		// 10 20 30 40 50 60 70 80 90for (auto e : myset){cout << e << " ";} cout << endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 >= 30auto itlow = myset.lower_bound(30);// 返回 > 60auto itup = myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout << e << " ";} cout << endl;return 0;
}

multiset与set的差异

        multiset 和 set 的使用基本完全类似，主要区别点在于 multiset 支持插入重复 key 值，那么 insert / find / count / erase 都围绕着支持插入重复 key 值而有所差异。

#include<iostream>
#include<set>
using namespace std;
int main()
{// 相⽐set不同的是，multiset只排序，不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;} cout << endl;// 相⽐set不同的是，x可以存储在多个，find查找的是中序的第⼀个。int x;cin >> x;auto pos = s.find(x);//遍历输出所有的x值while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;} cout << endl;// 相⽐set不同的是，count会返回x的实际个数。cout << s.count(x) << endl;// 相⽐set不同的是，erase给值时会删除所有的x。s.erase(x);for (auto e : s){cout << e << " ";} cout << endl;return 0;
}

set 容器练习题

1、两个数组的交集

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

提示：

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

解题思路：

        求两个数组的交集，根据题目描述可知重复的元素无需重复放入交集中。首先将两个数组放入 set 中去重并排序，得到两个没有重复元素的升序数组，然后使用两个set容器的迭代器遍历容器，如果两个元素相等，则尾插如定义好的新数组 v 中，并++两个迭代器，如果不相等则将较小元素的迭代器++，最后返回数组V。

代码演示：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> v;set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();while(it1 != s1.end() && it2 != s2.end()){if(*it1 > *it2){it2++;}else if(*it1 < *it2){it1++;}else{v.push_back(*it1);it1++;it2++;}}return v;}
};

 2、环形链表

        给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

  • 链表中节点的数目范围在范围 [0, 10^4] 内。
  • -10^5 <= Node.val <= 10^5。
  • pos 的值为 -1 或者链表中的一个有效索引。

解题思路：

        这道题在我们初学链表是就见过，当时我们使用的是快慢指针来解决的，现在有了set容器之后，解决这道题可谓是降维打击。我们只需定义一个ListNode*类型的set容器，遍历链表，如果遍历到相同的节点就说明该链表带环，否则不带环返回nullptr。注意，一定要使用指针类型，因为如果使用的是ListNode类型，其中的内容可能存在相等值，导致判断错误。 

 代码演示：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur){if(s.count(cur)){return cur;}else{s.insert(cur);}cur = cur->next;}return nullptr;}
};

map系列容器

map和multimap

参考文档：<map> 介绍- C++官方文档

map类的介绍

template < class Key,                  // map::key_typeclass T,                   // map::mapped_typeclass Compare = less<Key>, // map::key_compareclass Alloc = allocator<pair<const Key,T> > //map::allocator_type> class map;
  • map 声明如上，key 就是 map 底层关键字的类型。
  • T 是 map 底层 value 的类型。
  • set默认要求 key 支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第三个模板参数。
  • map底层存储数据的内存是从空间配置器申请的。
  • 一般情况下，我们都不需要传后面两个模板参数。
  • map 底层也是用红黑树实现的，增删查改的效率是O(LogN)，迭代器走的是中序遍历，所以是按key有序顺序遍历的。

pair类型介绍

        map 底层的红黑树节点中的数据，使用了 pair<Key, T> 的类模板存储键值对数据。

pair类模板部分源码如下：

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()){}pair(const T1& a, const T2& b) : first(a), second(b){}template<class U, class V>pair(const pair<U, V>& pr) : first(pr.first), second(pr.second){}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(T1 x, T2 y)
{return (pair<T1, T2>(x, y));
}

代码解读：

一、typedef pair<const Key, T> value_type;

        这行代码定义了一个类型别名 value_type，它代表一个由常量 Key 类型和T类型组成的 pair类型。

二、模板结构体 pair

  1. 类型定义部分：
    • typedef T1 first_type;和typedef T2 second_type;分别定义了两个类型别名，用于表示这个pair结构中第一个和第二个元素的类型。
  2. 成员变量部分：
    • T1 first;和T2 second;是这个结构的两个成员变量，分别代表pair中的第一个和第二个值。
  3. 构造函数部分：
    • pair() : first(T1()), second(T2()) {}是默认构造函数，它将第一个元素初始化为类型T1的默认值，第二个元素初始化为类型T2的默认值。
    • pair(const T1& a, const T2& b) : first(a), second(b) {}是带参数的构造函数，接受两个常量引用参数，分别用于初始化第一个和第二个元素。
    • template<class U, class V> pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {}是一个模板化的拷贝构造函数，它可以接受不同类型但具有相同结构的pair对象进行拷贝初始化。

三、函数模板 make_pair

  1. 这个函数模板接受两个参数T1类型的x和T2类型的y。
  2. return (pair<T1, T2>(x, y));语句创建一个新的pair<T1, T2>对象，并将其返回。这个函数通常用于方便地创建pair对象，而不需要显式地指定模板参数。 

map的函数接口

构造方法 

        map 支持正向和反向迭代遍历，遍历默认按 key 的升序顺序，因为底层是二叉搜索树的进阶（红黑树），迭代器走的是中序遍历；支持迭代器就意味着支持范围 for ，map 支持修改 value 数据，不支持修改 key 数据，因为修改关键字数据会破坏底层搜索树的结构。

// empty (1) ⽆参默认构造
explicit map(const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// range (2) 迭代器区间构造
template <class InputIterator>
map(InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type & = allocator_type());
// copy (3) 拷⻉构造
map(const map& x);
// initializer list (5) initializer 列表构造
map(initializer_list<value_type> il,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
// 迭代器是⼀个双向迭代器
//iterator -> a bidirectional iterator to const value_type
// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

增删查

        map 的插入接口在插入 pair 键值对数据时与 set 有所不同，查找和删除的接口只用到了 key 关键字，与 set 容器类似，find 中将返回值改为 iterator 即可，不仅可以确认 key 是否存在，还能找到  key 映射的 value 值，并可以通过迭代器进行修改value。

//Member types
//key_type -> The first template parameter(Key)
//mapped_type -> The second template parameter(T)
//value_type -> pair<const key_type, mapped_type>// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator, bool> insert(const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊
void insert(initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert(InputIterator first, InputIterator last);// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find(const key_type& k);// 查找k，返回k的个数
size_type count(const key_type& k) const;// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);// 删除k，k存在返回0，存在返回1
size_type erase(const key_type& k);// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

数据修改

        在之前我们提到 map 支持修改 mapped_type 数据，不支持修改 key 数据。map 的第一个修改操作是通过迭代器，迭代器遍历时通过 find 找到并返回 key 值所在的 iterator 修改， 但map 还有一个非常重要的修改接口 operator[]，不过 operator[] 不仅仅支持修改，还支持插入数据和查找数据，所以它是一个多功能复合接口，在后面讲解红黑树底层原理是我们会看到它的实现。

        需要注意从内部实现角度看，map 这里把我们传统说的 value 值（T），tyoedef 为了mapped_type 。而value_type 是红黑树节点中存储的 pair 键值对的值。日常中我们还是习惯将这里的T 写为value。

//Member types
//key_type -> The first template parameter(Key)
//mapped_type -> The second template parameter(T)
//value_type -> pair<const key_type, mapped_type>iterator find(const key_type& k);
// 查找k，返回k所在的迭代器，没有找到返回end()，
// 如果找到了通过iterator可以修改key对应的 mapped_type 值pair<iterator, bool> insert(const value_type& val);
// ⽂档中对insert返回值的说明
// insert插⼊⼀个pair<key, T>对象：
// 1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象
//first是key所在结点的迭代器，second是false
// 2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象
//first是新插⼊key所在结点的迭代器，second是true
// 也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
// 那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]
// 需要注意的是这里有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，
//另⼀个是insert返回值pair<iterator, bool>。mapped_type& operator[] (const key_type& k);
// operator的内部实现
mapped_type& operator[] (const key_type& k)
{// 1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储//mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ + 修改功能// 2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的//迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找 + 修改的功能pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

map接口的使用

构造与遍历

#include<iostream>
#include<map>
using namespace std;
int main()
{// initializer_list构造及迭代遍历map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插⼊"}, { "string", "字符串" } };//map<string, string>::iterator it = dict.begin();auto it = dict.begin();while (it != dict.end()){cout << (*it).first <<":"<<(*it).second << endl;		//解引用后引用pair内的值// map的迭代基本都使⽤operator->,这⾥省略了⼀个->// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取pair数据//cout << it.operator->()->first << ":" << it.operator->()-> second << endl;cout << it->first << ":" << it->second << endl;	//简化写法++it;} cout << endl;// insert插⼊pair对象的4种⽅式，对比之下，最后⼀种最⽅便//1、构造之后插入pair<string, string> kv1("first", "第⼀个");dict.insert(kv1);//2、使用pair匿名对象构造一个键值对插入dict.insert(pair<string, string>("second", "第⼆个"));//3、使用make_pair返回一个构造好的键值对dict.insert(make_pair("sort", "排序"));//4、C++11：initializer初始化列表->多参数构造支持隐式类型转换dict.insert({ "auto", "⾃动的" });// "left"已经存在，插⼊失败dict.insert({ "left", "左边，剩余" });// 范围for遍历for (const auto& e : dict){cout << e.first << ":" << e.second << endl;} cout << endl;string str;while (cin >> str){auto ret = dict.find(str);if (ret != dict.end()){cout << "->" << ret->second << endl;} else{cout << "⽆此单词，请重新输⼊" << endl;}} // erase等接⼝跟set完全类似，这⾥就不演⽰讲解了return 0;
}

迭代器

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利⽤find和iterator修改功能，统计⽔果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){// 先查找⽔果在不在map中// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}// 2、在，则查找到的节点中⽔果对应的次数++auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });} else{ret->second++;}} for (const auto & e : countMap){cout << e.first << ":" << e.second << endl;} cout << endl;return 0;
}

operator[]

#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{// 利⽤[]插⼊+修改功能，巧妙实现统计⽔果出现的次数string arr[] = { "苹果", "西⽠", "苹果", "西⽠", "苹果", "苹果", "西⽠","苹果", "⾹蕉", "苹果", "⾹蕉" };map<string, int> countMap;for (const auto& str : arr){// []先查找⽔果在不在map中// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 0}，同时返回次数的引⽤，++⼀下就变成1次了// 2、在，则返回⽔果对应的次数++countMap[str]++;} for (const auto & e : countMap){cout << e.first << ":" << e.second << endl;} cout << endl;return 0;
}int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在->插⼊ {"insert", string()}dict["insert"];// key不存在->插⼊+修改dict["left"] = "左边";// key存在->修改dict["left"] = "左边、剩余";// key存在->查找cout << dict["left"] << endl;return 0;
}

multimap 与 map 的差异

        这里与 set 和 multiset 的差异完全一样。multimap 和 map 的使用基本一致，区别点在于 multimap 支持 key 关键值的冗余，那么 insert / find / count / erase 都围绕着支持关键值 key 冗余有所差异。比如 find 查找时，有多个 key ，返回中序第一个。其次就是multimap 不支持 operator[] 修改，因为 key 值冗余， [] 就只能支持插入，不支持修改了。

map 容器的练习

1、随机链表的复制 

给你一个长度为 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 作为传入参数。

提示：

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

代码演示：

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {//第一步 拷贝节点map<Node*, Node*> m;Node* copyhead = nullptr;Node* copytail = nullptr;Node* cur = head;while(cur){if(copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}//原节点拷贝节点map kv存储m[cur] = copytail;cur = cur->next;}//第二步：拷贝randomcur = head;Node* copy = copyhead;while(cur){if(cur->random == nullptr){copy->random = nullptr;}else{copy->random = m[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};

 2、前K个高频单词

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

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

注意：

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

代码演示：

class Solution {
public:struct Compare{bool operator()(const pair<string, int>& x, const pair<string, int>& y) const{return x.second > y.second || (x.second == y.second && x.first < y.first);;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string, int> countMap;for(auto& e : words){countMap[e]++;} vector<pair<string, int>> v(countMap.begin(), countMap.end());// 仿函数控制降序,仿函数控制次数相等，字典序⼩的在前⾯sort(v.begin(), v.end(), Compare());// 取前k个vector<string> strV;for(int i = 0; i < k; ++i){strV.push_back(v[i].first);} return strV;}
};

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/476386.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【Xbim+C#】创建圆盘扫掠IfcSweptDiskSolid

【Xbim+C#】创建圆盘扫掠IfcSweptDiskSolid

基础回顾 https://blog.csdn.net/liqian_ken/article/details/143867404 https://blog.csdn.net/liqian_ken/article/details/114851319 效果图 代码示例 在前文基础上&#xff0c;增加一个工具方法&#xff1a; public static IfcProductDefinitionShape CreateDiskSolidSha…
阅读更多...
Flutter踩坑记录（三）-- 更改入口执行文件

Flutter踩坑记录（三）-- 更改入口执行文件

我们在flutter 中可能不习惯默认的lib/main.dart 作为入口文件&#xff0c;会修改成index.dart 或者修改main.dart的位置, 用Andorid studio开发 如果我们用Andorid studio开发&#xff0c;默认修改一下配置地址 运行项目即可。 用VSCode开发 如果我们使用VSCode开发&…
阅读更多...
AbsPlus框架介绍2

AbsPlus框架介绍2

ABSPlus框架以其集成的多功能性在市场上脱颖而出。它不仅提供美观且符合主流风格的页面设计&#xff0c;还支持灵活的流程配置&#xff0c;包括算法处理流程和页面审批流程。在众多业务系统中&#xff0c;流程管理往往是核心且复杂的挑战&#xff0c;涉及数据库设计、页面开发以…
阅读更多...
算法.图论-习题全集(Updating)

算法.图论-习题全集(Updating)

文章目录 本节设置的意义并查集篇并查集简介以及常见技巧并查集板子(洛谷)情侣牵手问题相似的字符串组岛屿数量(并查集做法)省份数量移除最多的同行或同列石头最大的人工岛找出知晓秘密的所有专家 建图及其拓扑排序篇链式前向星建图板子课程表 本节设置的意义 主要就是为了复习…
阅读更多...
使用docker快速部署Nginx、Redis、MySQL、Tomcat以及制作镜像

使用docker快速部署Nginx、Redis、MySQL、Tomcat以及制作镜像

文章目录 应用快速部署NginxRedisMySQLTomcat 制作镜像镜像原理基于已有容器创建使用 Dockerfile 创建镜像指令说明构建应用创建 Dockerfile 文件创建镜像 应用快速部署 Nginx docker run -d -p 80:80 nginx使用浏览器访问虚拟机地址 Redis docker pull redis docker run --…
阅读更多...
图像处理 之 凸包和最小外围轮廓生成

图像处理 之 凸包和最小外围轮廓生成

“ 最小包围轮廓之美” 一起来欣赏图形之美~ 1.原始图片 男人牵着机器狗 2.轮廓提取 轮廓提取 3.最小包围轮廓 最小包围轮廓 4.凸包 凸包 5.凸包和最小包围轮廓的合照 凸包和最小包围轮廓的合照 上述图片中凸包、最小外围轮廓效果为作者实现算法生成。 图形几何之美系列&#…
阅读更多...
Nuxt.js 应用中的 webpack：configResolved事件钩子

Nuxt.js 应用中的 webpack：configResolved事件钩子

title: Nuxt.js 应用中的 webpack：configResolved事件钩子 date: 2024/11/21 updated: 2024/11/21 author: cmdragon excerpt: 在 Nuxt.js 项目中，webpack:configResolved 钩子允许开发者在 Webpack 配置被解析后读取和修改该配置。这一钩子在所有 Webpack 配置被合并和确…
阅读更多...
java-贪心算法

java-贪心算法

1. 霍夫曼编码&#xff08;Huffman Coding&#xff09; 描述&#xff1a; 霍夫曼编码是一种使用变长编码表对数据进行编码的算法&#xff0c;由David A. Huffman在1952年发明。它是一种贪心算法&#xff0c;用于数据压缩。霍夫曼编码通过构建一个二叉树&#xff08;霍夫曼树&a…
阅读更多...
推荐一款专业电脑护眼工具：CareUEyes Pro

推荐一款专业电脑护眼工具：CareUEyes Pro

CareUEyes Pro是一款非常好用的专业电脑护眼工具&#xff0c;软件小巧&#xff0c;界面简单&#xff0c;它可以自动过滤电脑屏幕的蓝光&#xff0c;让屏幕显示更加的不伤眼&#xff0c;更加舒适&#xff0c;有效保护你的眼睛&#xff0c;可以自定义调节屏幕的色调&#xff0c;从…
阅读更多...
记录一下在原有的接口中增加文件上传☞@RequestPart

记录一下在原有的接口中增加文件上传☞@RequestPart

首先&#xff0c;咱声明一下&#xff1a; RequestBody和 MultipartFile 不可以 同时使用&#xff01;&#xff01;&#xff01; 因为这两者预期的请求内容类型不同。RequestBody 预期请求的 Content-Type 是 application/json 或 application/xml&#xff0c;而 MultipartFile …
阅读更多...
国标GB28181视频平台EasyCVR视频融合平台H.265/H.264转码业务流程

国标GB28181视频平台EasyCVR视频融合平台H.265/H.264转码业务流程

在当今数字化、网络化的视频监控领域&#xff0c;大中型项目对于视频监控管理平台的需求日益增长&#xff0c;特别是在跨区域、多设备、高并发的复杂环境中。EasyCVR视频监控汇聚管理平台正是为了满足这些需求而设计的&#xff0c;它不仅提供了全面的管理功能&#xff0c;还支持…
阅读更多...
JavaSrcipt 函数高级

JavaSrcipt 函数高级

一 原型与原型链 prototype 每个函数都有一个prototype属性, 它默认指向一个Object空对象(即称为: 原型对象或者显示原型) 原型对象prototype中有一个属性constructor, 它指向函数对象 function a(){}console.log(typeof a,typeof Date)console.log(a.prototype, Date.prot…
阅读更多...
蓝桥杯每日真题 - 第17天

蓝桥杯每日真题 - 第17天

题目&#xff1a;&#xff08;最大数字&#xff09; 题目描述&#xff08;13届 C&C B组D题&#xff09; 题目分析&#xff1a; 操作规则&#xff1a; 1号操作&#xff1a;将数字加1&#xff08;如果该数字为9&#xff0c;变为0&#xff09;。 2号操作&#xff1a;将数字…
阅读更多...
sysbench压测DM的高可用切换测试

sysbench压测DM的高可用切换测试

一、配置集群 1. 配置svc.conf [rootlocalhost dm]# cat /etc/dm_svc.conf TIME_ZONE(480) LANGUAGE(CN)DM(192.168.112.139:5236,192.168.112.140:5236) [DM] LOGIN_MODE(1) SWITCH_TIME(300) SWITCH_INTERVAL(200)二、编译sysbench 2.1 配置环境变量 [dmdba~]# vi ~/.bas…
阅读更多...
解决vue-pdf的签章不显示问题

解决vue-pdf的签章不显示问题

在使用vue-pdf 4.3.0时发现上传一般的普通pdf正常预览&#xff0c;但是上传带有红头文件的和和特殊字体的pdf无法正常内容显示&#xff0c;文字丢失问题。 1、查看控制台报错信息 2、缺少字体原因 getNumPages(url) {var loadingTask pdf.createLoadingTask({url: url,//引入…
阅读更多...
免费开源！DBdoctor推出开源版系统诊断工具systool

免费开源！DBdoctor推出开源版系统诊断工具systool

​前言 在开发和运维过程中&#xff0c;经常会遇到难以定位的应用问题&#xff0c;我们通常需要借助Linux系统资源监控工具来辅助诊断。然而&#xff0c;系统的IO、网络、CPU使用率以及文件句柄等信息通常需要通过多个独立的命令工具来获取。在没有部署如Prometheus这样的综合…
阅读更多...
Redis基本的全局命令

Redis基本的全局命令

在学习redis基本的全局命令之前呢&#xff0c;我们必须先进入redis-cli客户端才行。 如图&#xff1a; get和set get和set是redis两个最核心的命令。 get&#xff1a;根据key来获取value。 set&#xff1a;把key和value存储进去。 如set命令如图&#xff1a; 对于上述图中&…
阅读更多...
招商蛇口|在低密园林里，开启生活的“任意门”

招商蛇口|在低密园林里，开启生活的“任意门”

“最好的建筑是这样的&#xff0c;我们深处在其中,却不知道自然在哪里终了&#xff0c;艺术在哪里开始。” 凭借深耕西安10载的城市远见&#xff0c;以及建立在成功人居经验之上的敏锐洞察&#xff0c;招商蛇口将林语堂名言里的生活&#xff0c;变成了现实。 都市化越是加速&…
阅读更多...
2024年亚太数学建模竞赛问题C宠物产业及相关产业发展分析与对策

2024年亚太数学建模竞赛问题C宠物产业及相关产业发展分析与对策

随着人们消费理念的发展&#xff0c;随着经济的快速发展和人均收入的提高&#xff0c;宠物产业作为一个新兴产业在全球范围内逐渐积聚势头。1992年&#xff0c;中国小动物保护协会成立&#xff0c;随后1993年&#xff0c;皇家狗狗、玛氏等国际宠物品牌进入中国市场。随着“宠物…
阅读更多...
嵌入式面试八股文（九）·FreeRTOS与Linux的区别与相同点、多进程与多线程的区别、为什么项目使用多线程

嵌入式面试八股文（九）·FreeRTOS与Linux的区别与相同点、多进程与多线程的区别、为什么项目使用多线程

目录 1. FreeRTOS与Linux的区别与相同点 1.1 相同点 1.1.1 任务调度 1.1.2 多任务支持 1.1.3 内存管理 1.1.4 中断处理 1.1.5 同步机制 1.2 不同点 1.2.1 设计目标 1.2.2 实时性 1.2.3 内存管理 1.2.4 进程管理 1.2.5 多核支持 1.2.6 硬件支持 1.…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023