当前位置:   article > 正文

力扣 哈希表 总结_哈希表count函数

哈希表count函数

1. 杂项

哈希表的讲解,很细很细

定义一个哈希表

	unordered_map<typenameA,typenameB> hash; // key  value
  • 1

常用函数

	//增加元素
	hash[key] = value;
	//删除元素
	hash.erase(key);  //  如果没有找到会返回0
	//修改元素
	hash[key] = new value;
	//查找元素
	hash.find(key);   //  常用hash.find(key) == hash.end()来判断key值是否存在
	hash.count(key)   //  该函数:用以统计key值在unordered_map中出现的次数。c++ unordered_map不允许有重复的key。因此,如果key存在,则count返回1,如果不存在,则count返回0

	//————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
	//遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout <<"key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)  
        { 
            cout << (it->second)[i]<<' ';  //这边的value是vector<string>类型的,不能直接用cout打印
                                            //,所以要循环一个一个字符串打印出来
        }
        cout << endl;        
    }
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
	cout << "mp1" << mp1.count('b') << endl;
	使用count,返回的是被查找元素的个数。如果有,返回1;否则,返回0。注意,map中不存在相同元素,所以返回值只能是10。
	使用find,返回的是被查找元素的位置,没有则返回map.end()
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

2. emplace_back 函数解析

也是添加元素的函数,只不过和vector容器的push_back()的区别在于:
push_back()方法要调用构造函数和复制构造函数,这也就代表着要先构造一个临时对象,然后把临时的copy构造函数拷贝或者移动到容器最后面。而emplace_back()在实现时,则是直接在容器的尾部创建这个元素,省去了拷贝或移动元素的过程。

vector<pair<int, int>> ret;
ret.push_back(1,1)//会报错,因为没有构造一个临时对象
ret.push_back(pair(1,1))//不会报错,因为构成了一个pair对象
ret.emplace_back(1,1)//不会报错,因为直接在容器的尾部创建对象
  • 1
  • 2
  • 3
  • 4
vector<vector<int>> ans;
        int lastcol = INT_MIN;
        for (const auto& [col, row, value]: nodes) {
            if (col != lastcol) {
                lastcol = col;
                ans.emplace_back();//这里的emplace_back()直接在ans的尾部创建一个类型为vector<int>的空对象,如果省去这一行,后面的ans.back()会是一个空指针而报错。
            }
            ans.back().emplace_back(value);
        }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

3.哈希表的应用总结

3.1 力扣49 (字母异位词)

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

这边的键值对采用的是:由于互为字母异位词的两个字符串包含的字母相同,因此对两个字符串分别进行排序之后得到的字符串一定是相同的,故可以将排序之后的字符串作为哈希表的键。

    vector<string> strs;
    unordered_map<string, vector<string>> mp;
    strs.push_back("eat");
    strs.push_back("tea");
    strs.push_back("tan");
    strs.push_back("ate");
    strs.push_back("nat");
    strs.push_back("bat");
        
    for (string& str : strs) { //确定好排序好的key!
        string key = str;
        sort(key.begin(), key.end());
        mp[key].emplace_back(str);  //这边插入的key和value相对应!
    }

    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout <<"key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)  
        { 
            cout << (it->second)[i]<<' ';  //这边的value是vector<string>类型的,不能直接用cout打印
                                            //,所以要循环一个一个字符串打印出来
        }
        cout << endl;        
    }
    //排好序的结果如下图,最后按照下面的这个图 按照顺序放到 ans 里面就行了
    vector<vector<string>> ans;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        ans.emplace_back(it->second);
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

在这里插入图片描述

在这里插入图片描述

3.2 力扣49 法二 另一种键值对方式

给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

由于互为字母异位词的两个字符串包含的字母相同,因此两个字符串中的相同字母出现的次数一定是相同的,故可以将每个字母出现的次数使用字符串表示,作为哈希表的键。
由于字符串只包含小写字母,因此对于每个字符串,可以使用长度为 2626 的数组记录每个字母出现的次数。需要注意的是,在使用数组作为哈希表的键时,不同语言的支持程度不同,因此不同语言的实现方式也不同。

    vector<string> strs;
    strs.push_back("eat");
    strs.push_back("tea");
    strs.push_back("tan");
    strs.push_back("ate");
    strs.push_back("nat");
    strs.push_back("bat");
        
    vector<vector<string>> res;
    map<string, vector<string>> map;

    // 统计string的各字母频次,以频次为key直接加入队列
    for (auto s : strs) {
        string st = string(26, '0');  //先是弄成26个字母都是零
        for (auto c : s)  ++st[c - 'a']; //将有出现的字母对应的位置加 1
        map[st].emplace_back(s);  //放到键值对当中, st作为key是这个26个数   s作为value是正常的字符串
    }
    for (auto e : map)  res.emplace_back(e.second);  //放到 vector 当中

	//遍历方法
    for (auto it = map.begin(); it != map.end(); ++it)  //遍历的方法
    {
        cout << "key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)
        {
            cout << (it->second)[i] << ' ';  //这边的value是vector<string>类型的,不能直接用cout打印
                                            //,所以要循环一个一个字符串打印出来
        }
        cout << endl;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

在这里插入图片描述

3.3 力扣451 哈希表的深入理解

给定一个字符串 s ,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案,返回其中任何一个。

输入: s = “tree”
输出: “eert”
解释: 'e’出现两次,'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。
直接先按照字母出现的频率来创建哈希表,这样key为字母值,value为他出现的频率。
然后将其放到vector当中按照value的大小进行从大到小排序。
最后放到string reuslt当中即可。

	string s;
    s = "baafAAag";
    unordered_map<char, int> mp; //哈希表这样创建的,key是char类型,value是int类型
    int length = s.length();
    for (auto& ch : s) {
        mp[ch]++;  //这里怎么放key和value的!!很巧妙
    }
    //遍历哈希表元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout << "key为:" << it->first << "   value为:";
        cout << it->second;
        cout << endl;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

在这里插入图片描述

    vector <pair<char, int>> temp;  //创建内容格式和哈希表一致的vector容器,将哈希表的内容放到vector容器当中
    for (auto& it : mp) {
        temp.push_back(it); //格式一样,直接push_back
    }
    
    for (int i = 0; i < temp.size(); i++) {
        cout << temp[i].first << "  ";
        cout << temp[i].second << endl;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

在这里插入图片描述

    for (int i = 0; i < temp.size() - 1; ++i) {   //利用冒泡排序根据value的大小进行排序
        for (int j = 0; j < temp.size() - i - 1; ++j) {
            if (temp[j].second < temp[j+1].second)
            {
                pair<char, int> tempp;
                tempp = temp[j];
                temp[j ] = temp[j+1];
                temp[j+1] = tempp;
            }
        }
    }
    
    for (int i = 0; i < temp.size(); i++) {
    cout << temp[i].first << "  ";
    cout << temp[i].second << endl;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

    string result;  
    for (auto& it : temp) {
        result = result.append(it.second, it.first);  //最后按照顺序放到string reuslt当中即可
    }
    cout << result << endl;
  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述

2022年7月22日后

4 . 2022年7月22日后

#include <iostream>
using namespace std;
#include <string>
#include <unordered_map>
#include <algorithm>
#include<numeric>
#include<vector>
#include<cmath>
#include <unordered_set>
#include <set>

void print_mp1(unordered_map<char, vector<char>> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        
        cout << "mp1 --> key为:" << it->first << "   value为:";
        //cout << "key为:" << it->first << "   value为:" << it->second << endl;;

        for (int i = 0; i < it->second.size(); i++)
        {
            cout << (it->second)[i] << ' ';  //这边的value是vector<string>类型的,不能直接用cout打印
                                            //,所以要循环一个一个字符串打印出来
        }
        cout << endl;
    }
}

void print_mp2(unordered_map<char, char> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        
        cout << "mp2 --> key为:" << it->first << "   value为:" << it->second << endl;;
    }
}

void print_mp2(unordered_map<char, int> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {

        cout << "mp3 --> key为:" << it->first << "   value为:" << it->second << endl;;
    }
}

int main()
{   
    vector<int> nums1 = { 9,1,4,7,3,-1,0,5,8,-1,6};
    vector<int> nums2 = { 2,2,1,1 };
    
    set<int> s1;
    set<int> s2;
    for (int x : nums1) {
        s1.insert(x);
    }
    //for (auto it = s1.begin(); it != s1.end(); it++)
    //    cout << *it << " "<<endl;

    string pattern = "abcddabd";
    vector <char> str;
    string temp;

    //1.这种构造方式,可以用 emplace_back 函数来创造 , 也显示重复的数字
    unordered_map<char, vector<char>> mp1;
    for (int i = 0; i < pattern.size(); i++) {
        mp1[pattern[i]].emplace_back(pattern[i]);
    }
    print_mp1(mp1);
    cout << " " << endl;
    //2.计算key对应的数字,只会显示一个但是
    unordered_map<char, char> mp2;
    for (int i = 0; i < pattern.size(); i++) {
        mp2[pattern[i]] = pattern[i];
    }
    print_mp2(mp2);
    cout << " " << endl;
    //3. 计算每个key对应的重复数字的个数
    unordered_map<char, int> mp3;
    for (int i = 0; i < pattern.size(); i++) {
        mp3[pattern[i]]++;
    }
    print_mp2(mp3);
    cout << " " << endl;

    //print_mp(mp);
	system("pause");
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89

在这里插入图片描述

5. set容器横空出世

unordered_set是什么
unordered_set 容器,可直译为“无序 set 容器”。即 unordered_set 容器和 set 容器很像,唯一的区别就在于 set 容器会自行对存储的数据进行排序,而 unordered_set 容器不会。
unordered_set的几个特性:

  • 不再以键值对的形式存储数据,而是直接存储数据的值 ;
  • 容器内部存储的各个元素的值都互不相等,且不能被修改;
  • 不会对内部存储的数据进行排序

5.1 初始化构造

//set容器 构造和赋值
void PrintSet(unordered_set<int>& s)
{
    for (unordered_set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void PrintSet2(set<int>& s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
//1.初始化构造
    unordered_set<int> set1 = {1,2,3,4,5,67};
    cout << "unordered_set<int> set1 : ";
    PrintSet(set1);
    unordered_set<int> set2(set1);
    cout << "unordered_set<int> set2 : ";
    PrintSet(set2);
    unordered_set<int> set3(set1.begin(), set1.end()); //使用迭代器构造
    cout << "unordered_set<int> set3 : ";
    PrintSet(set3);
    unordered_set<int> set5(move(set2));
    cout << "unordered_set<int> set5 : ";
    PrintSet(set5);
    unordered_set<int> set6{ 1,2,10,10 }; //重复的自动去掉
    cout << "unordered_set<int> set6 : ";
    PrintSet(set6);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

在这里插入图片描述

5.2 插入数据(set和unordered_set的直接区别) (insert和emplace)

    set<int> st;
    st.insert(10);
    st.insert(20);
    st.insert(10);
    st.insert(40);
    st.insert(30);
    st.insert(30);
    cout << "set<int> st : ";
    PrintSet2(st);

    unordered_set<int> st1;
    st1.insert(10);
    st1.insert(20);
    st1.insert(10);
    st1.insert(40);
    st1.insert(30);
    st1.insert(30);
    cout << "unordered_set<int> st1 : ";
    PrintSet(st1);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

在这里插入图片描述

   set<int> st1;
    st1.insert(10);
    st1.insert(20);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
    st1.emplace(10);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

在这里插入图片描述

5.3 查找和统计

//3.查找和统计
    //- find(elem);    //查找elem是否存在,若存在则返回该元素的迭代器;若不存在,则返回set.end();
    //-count(elem);    //统计elem元素的个数 由于set容器中不允许含有重复元素,则值会返回0或者1;
    set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    set<int>::iterator it = s.find(40);
    if (it == s.end())
    {
        cout << "未找到该元素" << endl;
    }
    else
    {
        cout << "找到了该元素" << endl;
    }
    set<int> s1;
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(40);
    s1.insert(30);
    s1.insert(30);
    s1.insert(30);

    int num = s1.count(30);
    //对于set而言,由于set容器不能包含重复元素 所以count只能返回1或0
    cout << " num=" << num << endl;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

在这里插入图片描述

5.3 删除操作

    set<int> st;
    st.insert(10);
    st.insert(20);
    st.insert(10);
    st.insert(40);
    st.insert(30);
    st.insert(30);
    cout << "set<int> st : ";
    PrintSet2(st);
    //删除操作,成功返回1,失败返回0
    st.erase(10);
    cout << "st.erase(10) : ";
    PrintSet2(st);
    //删除操作,成功返回下一个pair的迭代器
    st.erase(st.find(20));
    cout << "st.erase(st.find(20)) : ";
    PrintSet2(st);
    //删除set1的所有元素,返回指向end的迭代器
    st.erase(st.begin(), st.end());
    cout << "st.erase(st.begin(), st.end()) : ";
    PrintSet2(st);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

在这里插入图片描述

    set<int> st1;
    st1.insert(10);
    st1.insert(20);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
    st1.clear();
    cout << "st1.clear() : ";
    PrintSet2(st1);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

在这里插入图片描述

5.4 set和multiset区别

    //set和multiset区别
    //set不可以插入重复数据,而multiset可以
    //set插入数据的同时会返回插入结果,1或者0,表示插入是否成功
    //multiset不会检测数据,因此可以插入重复数据
	set<int>s;
	pair<set<int>::iterator, bool> ret;

	//第一次插入10的时候可以成功插入
	ret = s.insert(10);
	if (ret.second)
	{
		cout << "插入成功" << endl;
	}
	else
	{
		cout << "插入失败" << endl;
	}

	//第二次插入10的时候,插入失败
	ret = s.insert(10);
	if (ret.second)
	{
		cout << "插入成功" << endl;
	}
	else
	{
		cout << "插入失败" << endl;
	}


	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);
	cout << "multiset<int> ms : ";
	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

在这里插入图片描述

6.lower_bound()、upper_bound()函数用法

#include <iostream>
using namespace std;
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>

void PrintSet2(set<int>& s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> nums = { 1,2,3,4,5,5,7,8,9,10 };
    int k = 1;
    int t = 100;

    int n = nums.size();
    set<int>st;
    for (int i = 0; i < n; i++) {
        st.insert(nums[i]);
    }
    PrintSet2(st);
    //cout << x2 <<endl;
    auto it = st.lower_bound(5);  //返回有序序列中大于等于key的第一个值的位置
    cout << *it <<endl;

    auto it1 = st.upper_bound(6);  //返回有序序列中大于key的第一个值的位置
    cout << *it1 << endl;
    
    //print_mp(mp);
	system("pause");
	return 0;
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40

在这里插入图片描述

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/469904
推荐阅读
相关标签
  

闽ICP备14008679号