从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)

简介: 从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别

从C语言C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(上):https://developer.aliyun.com/article/1521953

3.3 map的容量和操作函数

方括号是map的很特别的操作,其它不是连续空间存储的都没有,但是map的方括号和普通的也不一样,它返回的是键值对中key对应的value的引用。

当key不在map中时,通过operator[ ] 获取对应value时会发生什么问题?

在元素访问时,有一个与operator[ ]类似的操作:at()函数(该函数不常用),都是通过key找到与key对应的value然后返回其引用,

不同的是:当key不存在时,operator[ ]用默认value与key构造键值对然后插入,返回该默认value,at()函数直接抛异常。

上面方括号调用的那句代码分成两句就是这样:


3.4 map使用代码

用map来创建字典:

void test_map1()
{
  map<string, string> dict;
  //pair<string, string> kv1("sort", "排序");
  //dict.insert(kv1);
 
  dict.insert(pair<string, string>("sort", "排序")); // 等价于上面注释
  dict.insert(pair<string, string>("test", "测试"));
  dict.insert(pair<string, string>("string", "字符串"));
  typedef pair<string, string> DictKV;
  dict.insert(DictKV("string", "xxx"));
  dict.insert(make_pair("left", "左边")); // 常用这种插入
  dict["right"] = "右边"; // 更常用这种插入
 
  //map<string, string>::iterator it = dict.begin();
  auto it = dict.begin(); // 等价于上面注释
  while (it != dict.end())
  {
    //cout << (*it).first << (*it).second <<endl;
    cout << it->first << ":" << it->second << endl; // 等价于上面注释
    ++it;
  }
  cout << endl;
 
  for (const auto& kv : dict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << endl;
}
 
int main()
{
  //test_set();
  //test_multiset();
  test_map1();
 
  return 0;
}


用map来计算次数:

void test_map2()
{
  string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
  //map<string, int> countMap;
  //for (const auto& str : arr)
  //{
  //  map<string, int>::iterator it = countMap.find(str);
  //  if (it != countMap.end())
  //  {
  //    //(*it).second++;
  //    it->second++;
  //  }
  //  else
  //  {
  //    countMap.insert(make_pair(str, 1));
  //  }
  //}
  map<string, int> countMap;
  for (const auto& str : arr) // 等同于上面一大段注释
  {
    // 1、str不在countMap中,插入pair(str, int()),然后在对返回次数++
    // 2、str在countMap中,返回value(次数)的引用,次数++;
    countMap[str]++;
  }
 
  map<string, int>::iterator it = countMap.begin();
  while (it != countMap.end())
  {
    cout << it->first << ":" << it->second << endl;
    ++it;
  }
  cout << endl;
}
 
int main()
{
  //test_set();
  //test_multiset();
  //test_map1();
  test_map2();
 
  return 0;
}


3.5 multimap使用

multimap和multiset一样是允许键值冗余的,


1. multimap是关联式容器,它按照特定的顺序,存储由key和value映射成的键值对,其中多个键值对之间的key是可以重复的。

2. 在multimap中,通常按照key排序和惟一地标识元素,而映射的value存储与key关联的内容。key和value的类型可能不同,通过multimap内部的成员类型value_type组合在一起,value_type是组合key和value的键值对 :typedef pair value_type;

3. 在内部,multimap中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对key进行排序的。

4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢,但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。

5. multimap在底层用二叉搜索树(红黑树)来实现。

注意:multimap和map的唯一不同就是:map中的key是唯一的,而multimap中key是可以重复的。


multimap中的接口可以参考map,功能都是类似的。

注意:

1. multimap中的key是可以重复的。

2. multimap中的元素默认将key按照小于来比较

3. multimap中没有重载operator[ ]操作。

4. 使用时与map包含的头文件相同。

void test_multimap()
{
  map<string, string> dict;
  dict.insert(make_pair("sort", "排序"));
  dict["insert"];
  dict["insert"] = "插入";
  dict["left"] = "左边";
  dict["left"] = "左边";
  for (const auto& kv : dict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << dict.size() << endl;
 
  multimap<string, string> mdict;
  mdict.insert(make_pair("sort", "排序"));
  mdict.insert(make_pair("right", "右边"));
  mdict.insert(make_pair("right", "正确"));
  mdict.insert(make_pair("right", "右边")); // 正常插入,不管key值
  for (const auto& kv : mdict)
  {
    cout << kv.first << ":" << kv.second << endl;
  }
  cout << mdict.size() << endl;
}
 
int main()
{
  //test_set();
  //test_multiset();
  //test_map1();
  //test_map2();
  test_multimap();
 
  return 0;
}


4. 笔试OJ题

set和map在很多统计次数的OJ中都能用,这里先写两道:

692. 前K个高频单词 - 力扣(LeetCode)

难度中等


给定一个单词列表 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] 的数量]

进阶:尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
 
    }
};

priority_queue解析代码:

这道题是topk问题和统计次数的融合,就是先排次数(val)多的k个,次数一样多的按key排降序,

map里面是不管key的,这样我们就要写一个排序的仿函数了,先用优先级队列(堆)写一写:

优先级队列默认大的优先级高,传的是 less 仿函数,底层是一个大堆;

如果想控制小的优先级高,需手动传 greater 仿函数,其底层是一个小堆。

我们要弄一个大堆,大堆key一样的时候,按val弄一个小堆:

class Solution {
public:
    struct Less
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const
        {
            if(kv1.second < kv2.second) // second(int)升序,小的在前面就ture
            {
                return true;
            }
            if(kv1.second == kv2.second && kv1.first > kv2.first) // first(string)降序
            {
                return true;
            }
            return false;
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countMap;
        for(const auto& str : words) // 统计次数
        {
            countMap[str]++;
        }
 
        /*priority_queue<pair<string,int>,vector<pair<string,int>>,Less> MaxHeap;
        for(const auto& kv : countMap) // 也可以迭代器区间初始化,就是太长了,长就typedef
        {
            MaxHeap.push(kv);
        }*/
        typedef priority_queue<pair<string,int>,vector<pair<string,int>>,Less> MaxHeapType;
        MaxHeapType MaxHeap(countMap.begin(),countMap.end());
 
        vector<string> v;
        while(k--)
        {
            v.push_back(MaxHeap.top().first);
            MaxHeap.pop();
        }
        return v;
    }
};

sort解析代码:

在上面的基础上想想,如果我们用一个稳定的排序来排序string,是不是就能解决?

虽然sort不能排序map,但是可以把map转移到vector里然后在sort,直接sort是不稳定的,

但我们可以控制仿函数来间接控制:

(下面几种方法已经不是为了解题了,只是为了熟悉各个方法的使用,

因为priority的仿函数是反过来的,这里只需改下仿函数的大于小于号,把Less改成Great:)

class Solution {
public:
    struct Great
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const
        {
            if(kv1.second > kv2.second)
            {
                return true;
            }
            if(kv1.second == kv2.second && kv1.first < kv2.first)
            {
                return true;
            }
            return false;
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countMap;
        for(const auto& str : words) // 统计次数
        {
            countMap[str]++;
        }
 
        vector<pair<string,int>> sortV(countMap.begin(),countMap.end());
        sort(sortV.begin(),sortV.end(),Great());
 
        vector<string> v;
        for(int i = 0; i < k; ++i)
        {
            v.push_back(sortV[i].first);
        }
        return v;
    }
};

从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下):https://developer.aliyun.com/article/1521958

目录
相关文章
|
1天前
|
存储 Linux C语言
c++进阶篇——初窥多线程(二) 基于C语言实现的多线程编写
本文介绍了C++中使用C语言的pthread库实现多线程编程。`pthread_create`用于创建新线程,`pthread_self`返回当前线程ID。示例展示了如何创建线程并打印线程ID,强调了线程同步的重要性,如使用`sleep`防止主线程提前结束导致子线程未执行完。`pthread_exit`用于线程退出,`pthread_join`用来等待并回收子线程,`pthread_detach`则分离线程。文中还提到了线程取消功能,通过`pthread_cancel`实现。这些基本操作是理解和使用C/C++多线程的关键。
|
8天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
8天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
9天前
|
C语言 C++ 编译器
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
|
11天前
|
C++
c++语言核心技术要点,《运行时类型识别RTTI》
c++语言核心技术要点,《运行时类型识别RTTI》
17 2
|
9天前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
16天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
23 0
|
25天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
23 0
|
25天前
|
安全 C语言 C++
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(中)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
24 0
|
3天前
|
C++
C++一分钟之-类与对象初步
【6月更文挑战第20天】C++的类是对象的蓝图,封装数据和操作。对象是类的实例。关注访问权限、构造析构函数的使用,以及内存管理(深拷贝VS浅拷贝)。示例展示了如何创建和使用`Point`类对象。通过实践和理解原理,掌握面向对象编程基础。
30 2
C++一分钟之-类与对象初步