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

embedded/2024/11/23 0:17:15/

序列式容器和关联式容器

        在本篇文章之前，我们已经接触了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.ppmy.cn/embedded/139740.html

相关文章

C++ 并发专题 - 线程安全的单例模式

C++ 并发专题 - 线程安全的单例模式

一&#xff1a;概述&#xff1a; 在C编程中&#xff0c;call_once 是一种机制&#xff0c;用于确保某个函数或代码段在多线程环境下仅被调用一次。这种机制常用于初始化资源、配置全局变量或执行只需执行一次的逻辑。在 C11 标准中&#xff0c;std::call_once 是由标准库提供的…
阅读更多...
解读缓存问题的技术旅程

解读缓存问题的技术旅程

目录 前言1. 问题的突发与初步猜测2. 缓存的“隐身术”3. 缓存策略的深层优化4. 反思与感悟结语 前言 那是一个普通的工作日&#xff0c;团队例行的早会刚刚结束&#xff0c;我正准备继续优化手头的模块时&#xff0c;突然收到了用户反馈。反馈的内容是部分数据显示异常&#…
阅读更多...
Thymeleaf模板引擎生成的html字符串转换成pdf

Thymeleaf模板引擎生成的html字符串转换成pdf

依赖引入implementation("org.springframework.boot:spring-boot-starter-thymeleaf")implementation("org.xhtmlrenderer:flying-saucer-pdf")将ITemplateEngine注入到spring管理的类中&#xff0c; Context context new Context(); context.setVariable…
阅读更多...
【实用技能】使用 TX Text Control 创建带有嵌入式附件的 PDF 文档

【实用技能】使用 TX Text Control 创建带有嵌入式附件的 PDF 文档

TX Text Control .NET Server for ASP.NET&#xff08;下载试用最新版&#xff09;是一款Web应用程序的文档处理控件&#xff0c;包括用于 ASP.NET、ASP.NET Core 和 Angular 的文档编辑和查看的客户端包。目前TX Text Control .NET Server for ASP.NET 支持 .NET 5、.NET 6 和…
阅读更多...
uniapp 城市选择插件

uniapp 城市选择插件

uniapp城市选择插件 如上图 地址 完整demo <template><view><city-selectcityClick"cityClick":formatName"formatName":activeCity"activeCity":hotCity"hotCity":obtainCitys"obtainCitys":isSearch&quo…
阅读更多...
【系统架构设计师】真题论文: 论软件需求获取技术及应用（包括解题思路和素材）

【系统架构设计师】真题论文: 论软件需求获取技术及应用（包括解题思路和素材）

更多内容请见： 备考系统架构设计师-专栏介绍和目录 文章目录 真题题目（2011年 试题4）解题思路论文素材参考软件需求获取的目标与重要性软件需求获取技术软件需求获取技术的应用案例真题题目（2011年 试题4） 软件需求是指用户对新系统在功能、行为、性能、设计约束等方面的…
阅读更多...
学习路之phpstudy--安装mysql5.7后在my.ini文件中无法修改sql_mode

学习路之phpstudy--安装mysql5.7后在my.ini文件中无法修改sql_mode

windows环境下使用phpstudy安装mysql5.7后需要修改mysql中的sql_mode配置&#xff0c;但是在phpstudy中打开mysql配置文件my.ini后&#xff0c; 通过查找找不到sql_mode或sql-mode&#xff0c; 此时无法在my.ini文件中直接进行修改&#xff0c;可以使用mysql命令进行修改&#…
阅读更多...
数据分析-49-时间序列信息编码之采用虚拟变量

数据分析-49-时间序列信息编码之采用虚拟变量

文章目录 1 基本概念1.1 虚拟变量(one-hot)1.2 时间特征2 模拟数据2.1 日期序列2.2 目标序列3 编码虚拟变量(one-hot)3.1 年份编码3.2 月份编码3.3 星期几编码4 拟合模型4.1 构建数据集(每月编码)4.2 构建数据集(每日编码)5 参考附录1 基本概念 1.1 虚拟变量(one-hot) 虚拟变…
阅读更多...
最新文章

Copyright @ 2022~2023