哈希

std::set、std::multiset 的底层实现是红黑树,不是哈希表,但是std::set、std::multiset 依然使用哈希函数来做映射,只不过底层的符号表使用了红黑树来存储数据

这里在说一下,一些C++的经典书籍上 例如STL源码剖析,说到了hash_set hash_map,这个与unordered_set,unordered_map又有什么关系呢?

实际上功能都是一样一样的, 但是unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,hash_set,hash_map 是C++11标准之前民间高手自发造的*。

所以优先使用unordereed set 而不是hashset
如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法!

那有同学可能问了,遇到哈希问题我直接都用set不就得了,用什么数组啊。

直接使用set 不仅占用空间比数组大,而且速度要比数组慢,set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时,在数据量大的情况,差距是很明显的。

 vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);//返回一个数组实现了 交换对长度较小的元素进行操作的效果!!秒!1
        }
        unordered_map <int, int> m;
        for (int num : nums1) {//这个比 使用下标遍历的速度快很多
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {//查找在数组二中的数字
            if (m.count(num)) {//如果这个数字存在
                intersection.push_back(num);//放入这个数字到结果,有几次放几次
                --m[num];//并且对哈希表中的数字次数减一下
                if (m[num] == 0) {//减到0 就清楚这个记录,记得删除,因为m.count是存在就返回1,0也是存在,这样会按nums2计算
                    m.erase(num);
                }
            }
        }
        return intersection;

排序+双指针

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());//先进行排序
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        vector<int> intersection;
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {//双指针
            if (nums1[index1] < nums2[index2]) {//当这个素组指向的元素比拎一个素组的元素小,指往右边移动
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection.push_back(nums1[index1]);//如果相当就放入并同时往右边移动
                index1++;
                index2++;
            }
        }
        return intersection;
    }
};


哈希表happy number 判断是否循环出现了一个数,而这就涉及了查找操作,显然需要使用哈希表

unordered_set中的查找操作set.find()找不到会返回最后一个元素迭代器即set.end(),插入操作insert

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;
        }
    }
上一篇:难题精刷:寻找两个正序数组的中位数


下一篇:数据结构算法 | 单调栈