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;}
};新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！