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次的元素
给你一个整数数组 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
给定两个数组 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
给你两个整数数组 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.存在重复元素
给你一个整数数组 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.两句话中的不常见单词
句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。
如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。
给你两个 句子 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;
}
};新手写博客，有不对的位置希望大佬们能够指出，也谢谢大家能看到这里，让我们一起学习进步吧！
