C++从零开始(day52)——unordered_set,unordered_map学习使用

2024-03-17 16:52

本文主要是介绍C++从零开始(day52)——unordered_set,unordered_map学习使用,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.unordered系列关联式容器

C++98中,STL提供了底层为红黑树结构的一系列容器,在查找时效率可以达到时间复杂度可以达到O(logN),即红黑树的高度次,当树中的结点非常多时,查询效率也不理想,因此在C++11中,STL又提供了4个unordered系列的关联式容器,者四个容器与红黑树结构的关联式容器使用方法类似,只是其底层结构不同,这里只介绍unordered_set,unordered_map,关于unordered_multiset,unordered_multiset与其大同小异,这里不再花大量篇幅赘述

2.unordered_set,unordered_map的使用

与set,map相似,要注意的是

1.unordered_map,unordered_set遍历输出是无序的

2.unordered_map,unordered_set不支持反向迭代器

3.关于unordered_set,unordered_map的一些题目

1.在长度2N的数组中找出重复N次的元素

961. 在长度 2N 的数组中找出重复 N 次的元素

给你一个整数数组 nums ,该数组具有以下属性:

  • nums.length == 2 * n.
  • nums 包含 n + 1 个 不同的 元素
  • nums 中恰有一个元素重复 n 次

找出并返回重复了 n 次的那个元素

使用unordered_map计数,在遍历找出符合条件的数据返回即可

class Solution {
public:int repeatedNTimes(vector<int>& nums) {unordered_map<int, int> um;for(auto e : nums){++um[e];}int sz = nums.size();for(auto e : um){if(e.second == sz/2){return e.first;}}return 0;}
};

这是ac代码

2.两个数组的交集1

349. 两个数组的交集

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

因为输出结果中元素是唯一的,所以先利用unordered_set对其进行存储并去重,再遍历其中一个,在另一个中找元素是否存在来判断它是否需要输出

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){vector<int> ret;unordered_set<int> s1;unordered_set<int> s2;for(auto e : nums1)s1.insert(e);for(auto e : nums2)s2.insert(e);for(auto e : s1){if(s2.find(e) != s2.end())ret.push_back(e);}return ret;}
};

这是ac代码

3.两个数组的交集2

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序

由于输出元素中重复的要多次输出,并且按小的来,我们用unordered_map对其中一个vector的数据进行存储并计数,再遍历另一个数组,如果里面的数字可以找到,对计数位进行减减,压入输出vector中,最后输出

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {vector<int> v;unordered_map<int, int> um;for(auto e : nums1)++um[e];for(auto e : nums2){if(um[e]){--um[e];v.push_back(e);}} return v;}
};

这是ac代码

4.存在重复元素

217. 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ,返回 true ;如果数组中每个元素互不相同,返回 false

直接计数,如果计数位有大于等于2的返回false,反之返回true

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> um;for(auto e : nums){++um[e];if(um[e] >= 2)return true;}return false;}
};

这是ac代码

5.两句话中的不常见单词

884. 两句话中的不常见单词

句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。

如果某个单词在其中一个句子中恰好出现一次,在另一个句子中却 没有出现 ,那么这个单词就是 不常见的 

给你两个 句子 s1 和 s2 ,返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。

理解题目,不难有以下思路,将s1,s2加上空格后合并在一起,用unordered_map对其计数后返回只出现一次的单词即可

class Solution {
public:vector<string> uncommonFromSentences(string s1, string s2) {vector<string> ret;unordered_map<string, int> um;s1 += " ";s1 += s2;int begin = 0, end = 0;int sz = s1.size();while(end <= sz){if(s1[end] == ' ' || end == sz){string s;while(begin < end){s += s1[begin];++begin;}++um[s];++end;++begin;}else{++end;}}for(auto e : um){if(e.second == 1)ret.push_back(e.first);}return ret;}
};

新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!

这篇关于C++从零开始(day52)——unordered_set,unordered_map学习使用的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/819557

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传