哈希表——set（查重）

港控/mmm° 2023-09-23 22:33 26阅读 0赞

[349. 两个数组的交集 - 力扣（LeetCode）][349. _ - _LeetCode]

**由于unordered\_set底层实现为hash，故set内不会出现重复元素。**

虽然直接使用set 不仅占用空间比数组大，而且速度要比数组慢

但是，当数据十分分散时用set更好（比如1 2 3 100000000000000 1 90000000）

![da2a9cc17d694ae8a99f3c7d0407cc68.png][]

**这道题的数据不大，可以用数组**

**下面是unordered\_set的**

![eb6d617bcb7c48e2bfba6852653edf6c.png][]

class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            unordered_set<int>result_set;
            int hash[10001]={0};
            for(int i=0;i<nums1.size();i++)
            {
                hash[nums1[i]]=1;
            }
            for(int num:nums2)
            {
                if(hash[num]==1)
                result_set.insert(num);
            }
            return vector<int>(result_set.begin(),result_set.end());
        }//因为set有查重功能，所以返回result_set.begin(),result_set.end()
    };   //因为用了result_set.begin(),result_set.end()，所以前面得加上vector
    //体会一下这两个for循环的区别与联系

不使用数组

**初始化**

class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            unordered_set<int>result_set;
            unordered_set<int>nums_set(nums1.begin(),nums1.end());//必须初始化
            for(auto num:nums2)
            {
                if(nums_set.find(num)!=nums_set.end())
                {
                    result_set.insert(num);
                }
            }
            return vector<int>(result_set.begin(),result_set.end());
        }//set会查重，所以不会输出重复的
    };

**下面这个题一定要看一下，因为使用了set中不会出现重复元素**

[202. 快乐数 - 力扣（LeetCode）][202. _ - _LeetCode]

![7b306511e89b46d796954a1dc131962c.png][]

class Solution {
    public:
        // 取数值各个位上的单数之和
        int getSum(int n) {
            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            return sum;
        }
        bool isHappy(int n) {
            unordered_set<int> set;
            while(1) {
                int sum = getSum(n);
                if (sum == 1) {
                    return true;
                }
                // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
                if (set.find(sum) != set.end()) {
                    return false;
                } else {
                    set.insert(sum);
                }
                n = sum;
            }
        }
    };

[AcWing 4785. 奇偶 - AcWing][AcWing 4785. _ - AcWing]

![fe18aa128085425a933e9d5ead40703d.png][]

#include <iostream>
    #include <cstring>
    #include <set>
    
    using namespace std;
    
    int main()
    {
        string str;
        cin >> str;
    
        set<char> hash(str.begin(), str.end());
    
        if (hash.size() % 2) puts("odd");
        else puts("even");
    
        return 0;
    }

[349. _ - _LeetCode]: https://leetcode.cn/problems/intersection-of-two-arrays/
[da2a9cc17d694ae8a99f3c7d0407cc68.png]: https://img-blog.csdnimg.cn/da2a9cc17d694ae8a99f3c7d0407cc68.png
[eb6d617bcb7c48e2bfba6852653edf6c.png]: https://img-blog.csdnimg.cn/eb6d617bcb7c48e2bfba6852653edf6c.png
[202. _ - _LeetCode]: https://leetcode.cn/problems/happy-number/
[7b306511e89b46d796954a1dc131962c.png]: https://img-blog.csdnimg.cn/7b306511e89b46d796954a1dc131962c.png
[AcWing 4785. _ - AcWing]: https://www.acwing.com/activity/content/problem/content/7862/
[fe18aa128085425a933e9d5ead40703d.png]: https://img-blog.csdnimg.cn/fe18aa128085425a933e9d5ead40703d.png