当前位置: 首页 > news >正文

【C++从0到王者】第三十一站:map与set

文章目录

  • 一、关联式容器
  • 二、pair键值对
  • 三、set
    • 1. set的介绍
    • 2. set的部分接口以及应用
    • 3. count
    • 4. lower_bound和upper_bound
    • 5. equal_range
    • 6. multiset容器
  • 四、map
    • 1. map的介绍
    • 2. map的一些常见接口以及使用
    • 3. map的[]运算符重载
    • 4. 使用map改进一些题
    • 5. multimap容器
  • 五、map和set相关力扣题
  • 总结

一、关联式容器

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

那什么是关联式容器?它与序列式容器有什么区别?

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

二、pair键值对

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

stl里面对于pair的定义是这样的

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){}
};

image-20230914125013672

pair有三种构造函数,不难看出,分别是无参的构造,拷贝构造,以及通过两个值来进行构造

image-20230914125238633

除了三种构造函数以外,它还有一种方式,也可以生成pair对象。这个不是一个成员函数,所以可以直接使用。

image-20230914125152308

如上的一些构造函数的使用将在map中进行演示

三、set

1. set的介绍

如下图所示:

我们可以注意到它的模板参数是要比其他容器多一个的,这个容器我们也可以看到是一个仿函数。我们使用优先级队列的时候也用过这个仿函数

image-20230913133401959

集合是按照特定顺序存储唯一元素的容器。

在一个集合中,元素的值也标识它(值本身就是键,类型为 T),并且每个值必须是唯一的。集合中元素的值在容器中不能修改(元素总是 const 类型的),但是可以从容器中插入或删除元素。

在内部,集合中的元素总是按照其内部比较对象(类型为 Compare )指示的特定严格弱排序标准排序。

在通过键访问单个元素时,set 容器通常比 unordered_set 容器慢,但是它们允许基于次序对子集进行直接迭代。

集合通常以二叉搜索树的形式实现。这颗二叉搜索树是红黑树。

set其实就相当于key模型的二叉搜索树

注意:set里面的值是不可以被修改的,它实现这一点的原理就是将迭代器和const迭代器都是const迭代器没有任何区别。

image-20230913220104342

2. set的部分接口以及应用

image-20230913162515223

可以注意到,一共有三个构造函数,第一个是全缺省的默认构造函数,第二个是迭代器区间构造,第三个是拷贝构造。

不过这个拷贝构造的代价比较大,因为它是一个树的拷贝,而且析构也一样有很大的代价。

还有一个接口是insert

image-20230913164021039

这里的value_type就是T

image-20230913164051353

还有很多接口其实看一眼就大概知道啥意思

image-20230913164351420

比如如下代码:可以简单的测试一下代码

void test_set1()
{set<int> s;s.insert(1);s.insert(5);s.insert(2);s.insert(2);s.insert(2);s.insert(2);s.insert(4);s.insert(4);s.insert(4);s.insert(3);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;
}
int main()
{test_set1();return 0;
}

我们可以发现,set可以自动去重和排序

而它的去重原理就是:一个值已经有了,我们就不插入即可

image-20230913164841727

同时我们也可以试一下set的删除

image-20230913165335189

	auto pos = s.find(3);s.erase(pos);s.erase(4);for (auto e : s){cout << e << " ";}cout << endl;

image-20230913165525115

如上有演示了两种删除,从表面来看,看上去好像没有什么大的区别。我们可以认为下面的是通过上面的进行实现的。

不过在find中如果没有找到的话,是会直接报错的。

image-20230913165701465

而下面如果没有找到是什么也不会发生的

image-20230913165826881

不过我们可以加一个判断来解决这个问题

image-20230913165918446

这是因为find找不到会返回一个end迭代器导致的

image-20230913165955592

在容器中搜索与val等效的元素,如果找到则返回一个迭代器,否则返回一个迭代器给set::end。

但是我们知道算法库里面也有一个find,这个find似乎也能完成这个操作

image-20230913170208956

其实这两个find是存在一定的差异的,set里面的find是根据二叉搜索树的性质来进行查找的(其实是红黑树,效率更优),时间复杂度为O(logN),而算法库里面的find是一个一个查找的,时间复杂度为O(N)。

3. count

image-20230913180413649

count的作用是,给一个值,然后返回它出现了几次。不过因为set容器里面的值是唯一的,所以一个元素在这里面,返回1,否则返回0

如下的代码可以演示find和count寻找一个数据的使用

void test_set2()
{set<int> s;s.insert(1);s.insert(5);s.insert(2);s.insert(4);s.insert(4);s.insert(3);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;if (s.find(5) != s.end()){cout << "找到了" << endl;}if (s.count(5)){cout << "找到了" << endl;}
}
int main()
{test_set2();return 0;
}

image-20230913181028619

4. lower_bound和upper_bound

image-20230913184632056

返回迭代器到下界

返回一个迭代器,该迭代器指向容器中的第一个元素,该元素不被认为位于val之前(即,它要么等价,要么在val之后)。

该函数使用其内部比较对象(key_comp)来确定这一点,并返回一个迭代器,指向key_comp(element,val)将返回false的第一个元素。

如果用默认比较类型(less)实例化set类,则该函数返回一个指向不小于val的第一个元素的迭代器。

类似的成员函数upper_bound具有与lower_bound相同的行为,只是set包含一个与val等效的元素:在这种情况下,lower_bound返回一个指向该元素的迭代器,而upper_bound返回一个指向下一个元素的迭代器。

image-20230913184810676

返回迭代器到上界

返回一个迭代器,该迭代器指向容器中被认为在val之后的第一个元素。

该函数使用其内部比较对象(key_comp)来确定这一点,并返回一个迭代器,指向key_comp(val,element)将返回true的第一个元素。

如果用默认比较类型(less)实例化set类,则该函数返回指向第一个大于val的元素的迭代器。

类似的成员函数lower_bound具有与upper_bound相同的行为,只是set包含一个与val等效的元素:在这种情况下,lower_bound返回一个指向该元素的迭代器,而upper_bound返回一个指向下一个元素的迭代器。

我们可以使用这段代码来进行验证

void test_set3()
{std::set<int> myset;std::set<int>::iterator itlow, itup;for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90itlow = myset.lower_bound(30);                   itup = myset.upper_bound(60);                        myset.erase(itlow, itup);                     // 10 20 70 80 90for (auto e : myset){cout << e << " ";}cout << endl;
}
int main()
{test_set3();return 0;
}

image-20230913185131077

lower_bound和upper_bound一个设置为>=,一个设置为>。这样刚好可以将我们输入值所处的区间进行控制,刚好满足左闭右开。无论是构造也好,删除也好,插入也好都是刚好十分方便的。

5. equal_range

image-20230913190516431

获取相等元素的范围

返回一个范围的边界,该范围包括容器中与val等效的所有元素。

因为set容器中的所有元素都是唯一的,所以返回的范围最多只包含一个元素。

如果没有找到匹配项,则返回的范围长度为0,两个迭代器都指向容器内部比较对象(key_comp)认为在val之后的第一个元素。

如果容器的比较对象自反性地返回false(即,无论元素作为参数传递的顺序如何),则认为集合中的两个元素相等。

该函数返回一个pair,其成员pair::first是范围的下界(与lower_bound相同),pair::second是上界(与upper_bound相同)。

成员类型iterator和 const_iterator是指向元素的双向迭代器类型。

我们可以看这段代码

void test_set4()
{std::set<int> myset;for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;ret = myset.equal_range(35);std::cout << "the lower bound points to: " << *(ret.first) << '\n';std::cout << "the upper bound points to: " << *(ret.second)<< '\n';myset.erase(ret.first, ret.second);for (auto e : myset){cout << e << " ";}cout << endl;
}
int main()
{test_set4();return 0;
}

image-20230913191959527

这是因为这段区间内并不存在35,所以会返回一个比他大的数值所在的区间。且这两个是相等的。

如果我们要找的是等于30的区间的话,就是这样的

image-20230913192107827

由于set里面没有重复元素,所以其实只能找到那一个元素,从这个容器的角度来看,似乎这个寻找相等区间的函数并没有什么太大的用处,还不如find呢?

其实关于这些函数,主要还是为了另外一个容器设置的

6. multiset容器

在库里面set还有一种是multiset。

image-20230913192412125

这个容器是是一个允许键值冗余的一个容器,其接口和set一模一样。所以我们可以认为,刚刚的关于一些范围的容器,都是为了它而设计的

我们可以使用一下这个容器

void test_set5()
{multiset<int> s;s.insert(1);s.insert(5);s.insert(2);s.insert(2);s.insert(2);s.insert(2);s.insert(4);s.insert(4);s.insert(4);s.insert(3);multiset<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;//找到的是中序的第一个2,即排序的第一个2auto pos = s.find(2);while (pos != s.end()){cout << *pos << " ";pos++;}cout << endl;cout << s.count(2) << endl;auto ret = s.equal_range(2);cout << *ret.first << " " << *ret.second << endl;s.erase(ret.first, ret.second);for (auto e : s){cout << e << " ";}cout << endl;
}
int main()
{test_set5();return 0;
}

image-20230913193756397

关于上面这段代码作出如下解释:

首先这个是一个允许键值冗余的容器,所以相比于set就不会进行去重了。其余的功能和set是一样的。

由于find找的是中序的第一个2,所以我们从找到的那个开始进行打印,就会将从2以后的全部打印

其次我们的count也就可以计算出2的数量了。之前的在set中的count,由于set天然的去重了,所以只能用于检测是否存在某个值,而现在的话就可以统计数量了。

然后关于我们的找某个数的范围,这个函数也就可以查找2的所有范围了。于是我们就可以删除掉2所在的区间了。

所以count和equal_range这两个函数对于multiset容器而言更有意义。

四、map

1. map的介绍

如下所示,这个容器一共有四个参数,Key和T

image-20230913195205015

映射是关联容器,存储由键值和映射值按照特定顺序组合而成的元素。

在map中,键值通常用于排序和唯一标识元素,而映射值存储与该键相关联的内容。键和映射值的类型可能不同,组合在成员类型value_type中,这是一种组合了两者的pair类型:

typdef pair<const Key, T> value_type;

在内部,map中的元素总是按照键进行严格的弱排序,排序标准由内部比较对象(类型为Compare)表示。

在通过键访问各个元素时,Map容器通常比unordered_map容器慢,但它们允许根据键的顺序直接迭代子集。

映射后的值可以通过方括号运算符((operator[])直接访问。

映射通常以二叉查找树的形式实现。

这里的模板参数中,Key和T类似于key-val模型中的key和val的模板参数。这些模板类型都被define为了key_type和mapped_type。

同时还有value_type就相当于将这两个给结合到一块,放到了pair容器中。方便我们操控里面的数据,并且里面的key_type给的是const类型,这就说明了map中的key是不可以被修改的,但是value是可以被修改的

image-20230913215504385

2. map的一些常见接口以及使用

首先来看下insert,这个函数有三个重载,后两个是使用迭代器区间进行插入的。第一个是直接插入一个value_type类型的数据。value_type其实就是键值对,因为他是key-val模型的.

image-20230913221044418

通过插入新元素扩展容器,实际上是插入元素的数量增加了容器的大小。
因为map中元素的键是唯一的,所以插入操作会检查每个被插入元素的键是否与容器中已经存在的元素的键相等,如果相等,则不插入该元素,并返回一个指向该元素的迭代器(如果该函数有返回值)。
有关允许重复元素的类似容器,请参阅multimap。
在map中插入元素的另一种方法是使用成员函数map::operator[]。
在内部,map容器按照比较对象指定的标准对所有元素的键进行排序。元素总是按照这种顺序插入到其各自的位置。
这些参数决定了有多少个元素被插入,以及它们被初始化到哪些值

在这里我们可能会好奇的是,为什么我们插入的值必须且最好是pair类型的呢?将这两个数据连接到一起有什么好处吗?而我们在实现key-val模型的二叉搜索树的时候却不需要呢?其实这是因为我们的二叉搜索树并没有去实现迭代器。我们如果要写迭代器一定会涉及到这个迭代器的解引用问题。而此时,我们的key-val模型里面有两种数据,而c++并不支持返回多个参数,所以只能将这两个数据给合并起来从而得以实现。

对于这个函数的返回值,他返回的也是一个pair类型的对象。

如果插入的时候key已经在树里面,那么返回pair<树里面key的迭代器,false>

如果插入的时候key并未在树里面,那么返回pair<新插入key的迭代器,true>

所以insert从某种程度上也具有了查找的功能

如下代码所示,该段代码演示了我们对map里面插入数据的几种用法,我们可以直接传一个pair对象过去,也可以传pair的匿名对象,也可以使用make_pair函数来进行,当然我们可能会认为make_pair函数要通过调用一个函数来进行创建对象对否开销有点大,其实不是的,在这里编译器会直接将这个变成内联函数进行优化,实际效率相当于直接传入一个对象。除了前面三种以外,C++11还支持了多参数的构造函数隐式类型转换。所以我们可以直接使用多参数的构造函数隐式类型转换。

上面几种方式都是非常不错的,但是比较建议使用make_pair函数来创建。这个比较简洁,且有的C++编译器如果不支持C++11的话这个函数也是可以直接使用的。

在map里面我们取出的数据都是pair类型的,这是因为C++只能返回一个值,不能返回多个值。所以我们必须使用pair对象进行返回。然后C++也不支持pair的流插入和流提取,因为并没有进行重载。所以我们需要解引用后,拿到的只是一个结构体,我们还需要在访问里面的值。或者我们可以直接使用->也是很方便的。

void test_map1()
{map<string, string> dict;pair<string, string> kv1("insert", "插入");dict.insert(kv1);dict.insert(pair<string, string>("sort", "排序"));dict.insert(make_pair("remove", "改革"));dict.insert({ "process","过程" });//C++11 多参数的构造函数隐式类型转换map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << (*it).first << (*it).second << endl;cout << it->first << it->second << endl;it++;}for (const auto& e : dict){cout << e.first << " " << e.second << endl;}
}int main()
{test_map1();return 0;
}

image-20230914134139705

还需要注意的是,如果插入的时候,key相同,但是val不相同,是不会插入进去的,也不会覆盖进去的。即插入过程中,只比较key。key相同就不插入了。

上面是关于map的一些插入接口,还有一些接口是删除接口。也比较常见,三种删除,分别是直接删除某个迭代器位置的删除,或者给一个key去删除,注意不是val,只需要一个key就可以删除了。第三种就是删除一个迭代器区间。

image-20230914140314205

我们也可以注意到,查找和删除都只与key有关系,与其他无关。

还有如find,count这些接口也都是属于set的设计十分类似的

image-20230914141136778

获取元素的迭代器

在容器中搜索键值等于k的元素,如果找到则返回到该元素的迭代器,否则返回到map::end的迭代器。 如果容器的比较对象反射返回false,则认为两个键是等效的(即,无论元素作为参数传递的顺序如何)。 另一个成员函数map::count可以用来检查特定键是否存在。

如果找到具有指定键的元素,则返回该元素的迭代器,否则返回map::end。

如果map对象是const限定的,该函数返回一个const_iterator对象。否则,它返回一个迭代器。

image-20230914141155204

计算具有特定键的元素数量
在容器中搜索键等于 k 的元素,并返回匹配的数量。
由于 map 容器中的所有元素都是唯一的,因此该函数只能返回 1(如果找到元素)或 0(否则)。
如果容器的 comparison 对象反射返回 false,则认为两个键是等效的(即,无论作为参数传递的键的顺序如何)。

3. map的[]运算符重载

当我们使用map的insert接口和find接口的时候,我们可以来实现在之前二叉搜索树中的统计水果个数的代码。

void test_map2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto e : arr){map<string, int>::iterator pos = countMap.find(e);if (pos == countMap.end()){countMap.insert(make_pair(e, 1));}else{pos->second++;}}map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;it++;}
}int main()
{test_map2();return 0;
}

image-20230914144247781

但是事实上我们可以将代码变得更加简洁。

我们来看一下map的[]运算符重载

image-20230914144532877

访问元素

如果k与容器中某个元素的键匹配,则该函数返回对其映射值的引用。

如果k与容器中任何元素的键不匹配,则该函数用该键插入一个新元素,并返回对其映射值的引用。注意,这总是将容器的大小增加1,即使没有将映射值赋给元素(元素是使用其默认构造函数构造的)。

类似的成员函数map::at在具有键的元素存在时具有相同的行为,但在不存在时抛出异常。

调用此函数相当于:

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

简而言之,就是给一个key,如果这个key在map中存在,返回它的val,如果不存在,那么就创建一个pair对象插入进去,这个pair对象的first是key,pair中的second是val类型的默认构造函数。

这样我们就可以将上面代码简化为下面代码了。countMap对象中,它的两个参数是string和int,第一次的时候不存在,所以会创建一个pair<string,int>对象。int则会调用它的默认构造函数,即结果为0。然后有一个++,所以最终会将这个值给插入进去。

void test_map3()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto e : arr){countMap[e]++;}map<string, int>::iterator it = countMap.begin();while (it != countMap.end()){cout << it->first << ":" << it->second << endl;it++;}
}
int main()
{test_map3();return 0;
}

这个[]运算符重载其实就是靠插入函数实现的,因为无论插入成功与否,insert会返回一个pair对象,pair对象的first就是就是新插入进去结点或者已有结点的迭代器。然后我们直接访问这个迭代器指向的second即可。

除了上面的统计个数的场景,我们还可以试一下下面的单词翻译的场景

void test_map4()
{map<string, string> dict;pair<string, string> kv1("insert", "插入");dict.insert(kv1);dict.insert(pair<string, string>("sort", "排序"));dict.insert(make_pair("remove", "改革"));dict.insert({ "process","过程" });//C++11 多参数的构造函数隐式类型转换dict["remov"] = "xxx";dict["process"] = "进程";dict["access"] = "接受,道路";cout << (dict["set"] = "集合") << endl;for (auto e : dict){cout << e.first << " " << e.second << endl;}
}
int main()
{test_map4();return 0;
}

image-20230914151603007

我们可以注意到,通过[]运算符重载,我们可以实现对原来的值进行修改,如果原来没有可以插入。也可以进行查找+插入等等一系列操作。

4. 使用map改进一些题

力扣链接:有效的括号

对于下面这道题,我们之前就是直接一个一个匹配,但是现在,我们已经可以使用map来进行维护了,这样的话如果还有更多的括号需要进行匹配的话只需要改变map里面存储的值即可

class Solution {
public:bool isValid(string s) {stack<char> st;map<char,char> matchMap;matchMap['('] = ')';matchMap['['] = ']';matchMap['{'] = '}';for(auto ch : s){if(matchMap.count(ch)){st.push(ch);}else{if(st.empty()){return false;}char top = st.top();st.pop();if(matchMap[top]!=ch){return false;}}}if(!st.empty())return false;elsereturn true;}
};

力扣链接:复杂链表的复制

这道题如果有了map的话,简直是太简单了。直接建立一个映射关系,然后先复制好每一个结点,然后利用[]运算符重载就可以很好的处理好每一个之间的关系。

/*
// 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) {Node* cur = head;map<Node*,Node*> listMap;while(cur){listMap[cur] = new Node(cur->val);cur = cur->next;}cur = head;while(cur){listMap[cur]->next = listMap[cur->next];listMap[cur]->random = listMap[cur->random];cur = cur->next;}return listMap[head];}
};

5. multimap容器

这个容器与map之间的关系就好像set与multiset之间的关系一样。接口都是一样的,不同的就是这个容器允许重复元素出现

还有一共不同就是这个容器没有提供[]运算符重载了,其实也是比较合理的,因为此时一个key可以有很多个val,是没法确定要哪一个的。

insert也有一些变化,他的返回值就不在是一共pair了,里面就没有所谓的bool了,只是单纯的返回新插入结点的迭代器,因为他插入永远成功

image-20230914161926246

那么既然一个key可以有多个val,我们可以注意到他是可以根据key进行删除的,那么它是全删除掉吗?确实是这样的,multimap根据一个值去删除元素会将所有与key相关的全部删除掉。

image-20230914162223202

五、map和set相关力扣题

力扣链接:两个数组的交集

这道题目求的是交集,我们的思路就是利用set来完成最为方便。首先先将两个数组里面的值都丢到set里面,可以天然的去重。然后我们再去遍历这两个set。由于正好也排好序了。所以我们就如果谁小,谁就++,否则相等的话,那么就进入数组,然后两个同时++即可

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> v;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;}
};

如果题目要让我们求差集的话,也是很简单的,我们还是先丢到set里面,然后进行比对,将较小的进入数组,然后++。如果相等同时++即可。因为set天然的排好序了,所以,小的一定是独一无二的,而较大的,当小的++以后,可能就会出现重复了。

力扣链接:前K个高频单词

对于这道题,我们的思路也是比较简单的,我们首先先创建一个map,然后我们将words中的所有单词给放入map中,顺便统计好次数。这样以后,map中也正好天然的按照字典序排好了。接下来我们需要对map中的数据按照频率进行排序。不过这里的排序需要注意,我们不能直接对map进行排序,因为迭代器的类型不匹配。所以我们只能将数据都放入一个vector<pair<string,int>>中进行排序。在这里还有一个大坑,首先我们要按照降序排列,所以我们会写一个仿函数,让他按照降序排,其次这里我们不能直接用sort,因为sort底层是一个快排,它是不稳定的,会将字典序顺序打乱。所以我们需要使用一个稳定的排序,库里面正好提供了这个稳定的排序stable_sort。所以这下排序之后,我们就能完成这个题目了。

class Solution {
public:struct Greater{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second>p2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;vector<string> v;for(auto& e : words){countMap[e]++;}vector<pair<string,int>> vpa(countMap.begin(),countMap.end());stable_sort(vpa.begin(),vpa.end(),Greater()); for(int i = 0; i < k; i++){v.push_back(vpa[i].first);}return v;}
};

上面最坑人的地方莫过于sort不是稳定的排序,我们可能甚至都没用过stable_sort这个排序。那么在我们不知道的情况下,该如何处理这道题呢?事实上,我们会发现,我们的仿函数其实还可以在详细一些,我们先按频率排,当频率相等的时候,在依据字典序排列即可

class Solution {
public:struct Greater{bool operator()(const pair<string,int>& p1,const pair<string,int>& p2){return p1.second>p2.second||((p1.second==p2.second)&&(p1.first<p2.first));}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;vector<string> v;for(auto& e : words){countMap[e]++;}vector<pair<string,int>> vpa(countMap.begin(),countMap.end());sort(vpa.begin(),vpa.end(),Greater()); for(int i = 0; i < k; i++){v.push_back(vpa[i].first);}return v;}
};

在这里其实还有第三种方式可以完成这道题

如下代码所示,我们可以先将countMap以字典序排好且统计出次数之后,然后使用一个multimap<int,string,greater<int>>以频率在排一次。注意使用第三个模板参数,即仿函数,因为我们是要以频率为降序进行排序。然后最后我们依次插入vector即可

class Solution {
public:vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> countMap;vector<string> v;for(auto& e : words){countMap[e]++;}multimap<int,string,greater<int>> sMap;for(auto& e : countMap){sMap.insert(make_pair(e.second,e.first));}auto it = sMap.begin();while(k--){v.push_back(it->second);it++;}return v;}
};

总结

本节主要讲解了map与set的基本使用。希望能对大家带来帮助!

相关文章:

【C++从0到王者】第三十一站:map与set

文章目录 一、关联式容器二、pair键值对三、set1. set的介绍2. set的部分接口以及应用3. count4. lower_bound和upper_bound5. equal_range6. multiset容器 四、map1. map的介绍2. map的一些常见接口以及使用3. map的[]运算符重载4. 使用map改进一些题5. multimap容器 五、map和…...

生产消费者模型的介绍以及其的模拟实现

目录 生产者消费者模型的概念 生产者消费者模型的特点 基于阻塞队列BlockingQueue的生产者消费者模型 对基于阻塞队列BlockingQueue的生产者消费者模型的模拟实现 ConProd.c文件的整体代码 BlockQueue.h文件的整体代码 对【基于阻塞队列BlockingQueue的生产者消费者模型…...

Unity ML-Agents默认接口参数含义

下面的含义就是训练中常用的yaml文件&#xff1a; behaviors:waffle:trainer_type: ppo #训练器类型&#xff0c;默认ppo。还有sac和pocahyperparameters:batch_size: 64 # 梯度下降每次迭代的经验数。应确保该值总是比 buffer_size小几倍。 在使用连续动作的情况下&#x…...

【python数据分析基础】—pandas中loc()与iloc()的介绍与区别

文章目录 前言一、loc[]函数二、iloc[]函数三、详细用法loc方法iloc方法 总结共同点不同点 前言 我们经常在寻找数据的某行或者某列的时常用到Pandas中的两种方法iloc和loc&#xff0c;两种方法都接收两个参数&#xff0c;第一个参数是行的范围&#xff0c;第二个参数是列的范…...

ad18学习笔记十一:显示和隐藏网络、铺铜

如何显示和隐藏网络&#xff1f; Altium Designer--如何快速查看PCB网络布线_ad原理图查看某一网络的走线_辉_0527的博客-CSDN博客 AD19(Altium Designer)如何显示和隐藏网络 如何显示和隐藏铺铜&#xff1f; Altium Designer 20在PCB中显示或隐藏每层铺铜-百度经验 AD打开与…...

全国职业技能大赛云计算--高职组赛题卷④(私有云)

全国职业技能大赛云计算--高职组赛题卷④&#xff08;私有云&#xff09; 第一场次题目&#xff1a;OpenStack平台部署与运维任务1 基础运维任务&#xff08;5分&#xff09;任务3 OpenStack云平台运维&#xff08;15分&#xff09;任务4 OpenStack云平台运维开发&#xff08;1…...

Camera Tunning ISP 模块面试总结

一.ISP的调试流程概述&#xff1a; 在ISP调试流程中&#xff0c;我们首先需要确认以下三个方面&#xff1a;项目需求、硬件问题确认和Sensor驱动配置确认。 项目需求方面&#xff0c;即Sensor需要出多大的分辨率去调效果&#xff1b;因为有些芯片有最大分辨率支持的限制&#x…...

AOSP源码中Android.mk文件中的反斜杠符号(\)的作用和使用

简介 在AOSP&#xff08;Android Open Source Project&#xff09;源码中的Android.mk文件中&#xff0c;反斜杠符号&#xff08;\&#xff09;的主要作用是将一行代码拆分成多行&#xff0c;以提高可读性并帮助组织较长的代码块。这对于定义复杂的构建规则和变量时特别有用。…...

如何查看mysql的存储引擎

要查看MySQL中的存储引擎&#xff0c;可以使用以下两种方法&#xff1a; 1. 使用 SQL 查询&#xff1a; 您可以使用SQL查询来查看MySQL中的存储引擎。打开MySQL客户端&#xff0c;并连接到您的MySQL服务器&#xff0c;然后运行以下SQL查询&#xff1a; SHOW TABLE STATUS;这…...

FPGA project : dht11 温湿度传感器

没有硬件&#xff0c;过几天上板测试。 module dht11(input wire sys_clk ,input wire sys_rst_n ,input wire key ,inout wire dht11 ,output wire ds ,output wire …...

std::string和QString的区别以及互转

一 区别 1.字符编码支持 std::string&#xff1a;默认情况下&#xff0c;使用 ASCII 或 UTF-8 编码。不直接提供对多字节字符的内置支持。 QString&#xff1a;提供对多种字符编码的支持&#xff0c;包括 ASCII、UTF-8、UTF-16 等。它更适合处理国际化和本地化的字符串。 2.…...

python+vue理发店管理系统

理发店管理系统主要实现角色有管理员和会员,管理员在后台管理用户表模块、token表模块、收藏表模块、商品分类模块、热卖商品模块、活动公告模块、留言反馈模块、理发师模块、会员卡模块、会员充值模块、会员模块、服务预约模块、服务项目模块、服务类别模块、热卖商品评论表模…...

基于微信小程序的个人健康管理系统的设计与实现(源码+lw+部署文档+讲解等)

前言 &#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计划导师、全栈领域优质创作者&#xff0c;博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f447;&#x1f3fb;…...

共聚焦显微镜在化学机械抛光课题研究中的应用

两个物体表面相互接触即会产生相互作用力&#xff0c;研究具有相对运动的相互作用表面间的摩擦、润滑与磨损及其三者之间关系即为摩擦学&#xff0c;目前摩擦学已涵盖了化学机械抛光、生物摩擦、流体摩擦等多个细分研究方向&#xff0c;其研究的数值量级也涵盖了亚纳米到百微米…...

本地Linux 部署 Dashy 并远程访问

文章目录 简介1. 安装Dashy2. 安装cpolar3.配置公网访问地址4. 固定域名访问 转载自cpolar极点云文章&#xff1a;本地Linux 部署 Dashy 并远程访问 简介 Dashy 是一个开源的自托管的导航页配置服务&#xff0c;具有易于使用的可视化编辑器、状态检查、小工具和主题等功能。你…...

互联网摸鱼日报(2023-09-18)

互联网摸鱼日报(2023-09-18) 36氪新闻 最前线 | 号外电摩12.68万元起订&#xff0c;配16.9度一体压铸电池包 本周双碳大事&#xff1a;CCER交易管理办法获生态环境部原则通过&#xff1b;明阳斥资100亿元加码光伏项目&#xff1b;“全路程”获2亿元D轮融资 200亿&#xff0c…...

Kotlin中函数的基本用法以及函数类型

函数的基本用法 1、函数的基本格式 2、函数的缺省值 可以为函数设置指定的初始值&#xff0c;而不必要传入值 private fun fix(name: String,age: Int 2){println(name age) }fun main(args: Array<String>) {fix("张三") }输出结果为&#xff1a;张三2 …...

在macOS使用VMware踩过的坑

目录 MAC提示将对您的电脑造成伤害/MAC OS 升级到10.15.3后vmware虚拟机黑屏 mac系统下&#xff0c;vm虚拟机提示打不开/dev/vmmon mac VMware Workstation 在此主机上不支持嵌套虚拟化 mac VMware清理虚拟机空间​​​​​​​ MAC提示将对您的电脑造成伤害/MAC OS 升级到…...

构建健壮的Spring MVC应用:JSON响应与异常处理

目录 1. 引言 2. JSON 1. 轻量级和可读性 2. 易于编写和解析 3. 自描述性 4. 支持多种数据类型 5. 平台无关性 6. 易于集成 7. 社区支持和标准化 3. 高效处理异常 综合案例 异常处理方式一 异常处理方式二 异常处理方式三 1. 引言 探讨Spring MVC中关键的JSON数据…...

那些配置服务器踩的坑

最近在配置内网&#xff0c;无外网的服务器&#xff0c;纯纯记录一下踩得坑&#xff0c;希望看到的人不要再走这条弯路。 ------------------------------------------------------------------------------------------------------------------------------- 任务&#xff…...

交换机端口镜像详解

交换机端口镜像是一种网络监控技术&#xff0c;它允许将一个或多个交换机端口的网络流量复制并重定向到另一个端口上&#xff0c;以便进行流量监测、分析和记录。通过端口镜像&#xff0c;管理员可以实时查看特定端口上的流量&#xff0c;以进行网络故障排查、安全审计和性能优…...

Spring源码分析(三) IOC 之 createBean()和doCreateBean()

a、在createBean中又是主要做了什么事情&#xff1f; 完成bean得创建&#xff0c;填充属性、循环依赖 、aop等一系列过程 1、createBean() 在createBean中主要干了3件事情 1、解析class -> resolveBeanClass() 2、验证及准备覆盖的方法,lookup-method replace-method -> …...

【鸿蒙(HarmonyOS)】UI开发的两种范式:ArkTS、JS(以登录界面开发为例进行对比)

文章目录 一、引言1、开发环境2、整体架构图 二、认识ArkUI1、基本概念2、开发范式&#xff08;附&#xff1a;案例&#xff09;&#xff08;1&#xff09;ArkTS&#xff08;2&#xff09;JS 三、附件 一、引言 1、开发环境 之后关于HarmonyOS技术的分享&#xff0c;将会持续使…...

Flink中的批和流

批处理的特点是有界、持久、大量&#xff0c;非常适合需要访问全部记录才能完成的计算工作&#xff0c;一般用于离线统计。 流处理的特点是无界、实时, 无需针对整个数据集执行操作&#xff0c;而是对通过系统传输的每个数据项执行操作&#xff0c;一般用于实时统计。 而在Flin…...

【LeetCode-中等题】150. 逆波兰表达式求值

文章目录 题目方法一&#xff1a;栈 题目 方法一&#xff1a;栈 class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deque new LinkedList<>();String rpn "-*/";//符号集 用来判断扫描的是否为运算符int sum 0;for(int i 0 ; i…...

搭建ELK+Filebead+zookeeper+kafka实验

部署 Zookeeper 集群 准备 3 台服务器做 Zookeeper 集群 192.168.10.17 192.168.10.21 192.168.10.22 1.安装前准备 关闭防火墙 systemctl stop firewalld systemctl disable firewalld setenforce 0 安装 JDK yum install -y java-1.8.0-openjdk java-1.8.0-openjdk-…...

java专题练习(抢红包)

package 专题练习;import java.util.Random;public class grab_red_packet {/* 需求:直播抽奖,分别由{2,588,888,1000,10000}五个奖金,请用代码模拟抽奖,奖项出现顺序要随机且不重复打印效果:588元的奖金被抽出*///思路://1. 先用数组把奖金定义好//2. 用random方法给出随机数索…...

AVR 单片机 调试环境 JTAG MKII

注意 驱动 的厂家: 如果驱动备改变为其他厂家的驱动 就与 AVR Studio7不兼容 保证驱动选择正确是 能够使用硬件调试的关键 如果驱动不对&#xff0c;使用 USB驱动修改工具 修改 比如 UsbDriverTool.exe...

C++ - AVL树实现(下篇)- 调试小技巧

前言 本博客是 AVL树的下篇&#xff0c;上篇请看&#xff1a;C - AVL 树 介绍 和 实现 &#xff08;上篇&#xff09;_chihiro1122的博客-CSDN博客 上篇当中写插入操作&#xff0c;和其中涉及的 旋转等等细节&#xff0c;还有AVL树的大体框架。 调试小技巧 条件断点 在大项目…...

Mybatis懒加载

懒加载是什么&#xff1f; 按需加载所需内容&#xff0c;当调用到关联的数据时才与数据库交互否则不交互&#xff0c;能大大提高数据库性能&#xff0c;并不是所有场景下使用懒加载都能提高效率。 Mybatis懒加载&#xff1a;resultMap里面的association、collection有延迟加载功…...

有谁认识做微网站的/辽宁网站建设

我们的一些业务数据&#xff0c;有些定义的是按某个分割符分割数据&#xff0c;然后一行一行的&#xff0c;处理这种数据时候&#xff0c;要务必小心&#xff0c;因为它简单&#xff0c;不用维护类似json格式的数据或者一个对象&#xff0c;而是直接通过下标位置来访问数据的&a…...

网站建设的市场需求/win优化大师官网

下载地址&#xff1a;http://code.google.com/p/freecms/ 站点管理 FreeCMS支持网站群模式,并支持无限树级管理。 1. 添加一级站点 从左侧管理菜单点击站点管理进入。 提示&#xff1a;只有admin才可以进行“添加一级站点”操作。 点击“添加一级站点” 输入相关属性点击“保存…...

html学校网站模板/seo优化技术排名

国密算法 国密即国家密码局认定的国产密码算法&#xff0c;即商用密码。 国密算法是国家密码局制定标准的一系列算法。其中包括了对称加密算法&#xff0c;椭圆曲线非对称加密算法&#xff0c;杂凑算法。具体包括SM1,SM2,SM3等&#xff0c;其中&#xff1a; SM2为国家密码管理…...

南山优化网站建设案例/推广软件排行榜前十名

本地广播和全局广播(按照传播范围) 本地广播(app内部传播)数据,其它app收不到,保证了数据的安全性 全局广播,可以在整个手机所有App之间传播通信,会有安全性问题。普通广播默认就是全局广播。 例如监听开机充电打电话发短信修改时间这些 1.本地广播只能通过动态注册 2.本地广播…...

wordpress文件大小限制/投百度做广告效果怎么样

http://v.youku.com/v_show/id_XMzA0NTgyMDU2.html 在百度&#xff0c;有这么一个部门&#xff0c;有这么一群工程师&#xff1b; 他们面对着百度巨大的流量所带来的技术挑战&#xff1b; 他们每天思考研究着如何让百度更快更稳定&#xff1b; 他们做到了&#xff0c;他们支撑了…...

做个视频网站/推广链接点击器网页

Description 物流公司要把一批货物从码头A运到码头B。由于货物量比较大&#xff0c;需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线&#xff0c;以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在&#xff0c;有的时候…...