算法刷题--哈希表--字母异位词和两个数组的交集

哈希表概念

哈希表是根据关键码的值而直接进行访问的数据结构。 直白来讲数组就是一种哈希表。 那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。 那么一般都是将一个集合里面的元素映射为哈希表的索引。 那么设计哈希表的时候需要考虑以下原则：均匀性，尽可能让不同key均匀分布到哈希表中；高效性；覆盖性，确保所有key都能映射到哈希表范围内。 当多个元素映射到同一个索引时，这种现象叫做哈希碰撞。 解决哈希碰撞有两种方法：

拉链法，发生冲突的元素都被存储在链表中，这样可以通过索引找到冲突的元素了。这样做就及不会因为数组空值而浪费大量内存，又不会因为链表太长而在查找上浪费太多时间。

线性探测法，这种方法一定要保证tablesize要大于datasize,冲突了那么就找下一个空位放置冲突的元素。

常见的三种哈希结构 数组setmap 当我们使用哈希法来解决问题的时候， 集合底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::set红黑树有序否否O(log n)O(log n)std::multiset红黑树有序是否O(log n)O(log n)std::unordered_set哈希表无序否否O(1)O(1)

set的键值和实值时一个东西，既时键值又是实值。是一个双向迭代器，只能it+±-，不能it+2.

映射底层实现是否有序数值是否可以重复能否更改数值查询效率增删效率std::map红黑树key有序key不可重复key不可修改O(log n)O(log n)std::multimap红黑树key有序key可重复key不可修改O(log n)O(log n)std::unordered_map哈希表key无序key不可重复key不可修改O(1)O(1)

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset。

有效字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

eg: 输入: s = “anagram”, t = “nagaram” 输出: true

要点

这道题目总共就26个字母，限制了范围的，那么就直接用数组实现很简单，映射通过ASCII码实现。

#include <vector> class Solution { public: bool isAnagram(string s, string t) { vector<int> record(26,0); //因为是只判断字母，所以只有26个索引就行了 for (int i = 0; i < s.size(); i++) { record[s[i] - 'a']++; //如果是a那就是0，利用了字母ASCII码中递增 } for (int j = 0; j < t.size(); j++) { record[t[j] - 'a']--;//再依次遍历所有t中的，利用-- } for (auto iter = record.begin(); iter != record.end(); iter++) { if(*iter != 0) { return false; } } return true; } }; 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

这里就最好不使用数组，但因为题目规定了大小在1000.因此也可以用数组的方式实现。

利用unordered_set实现： class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result_set; unordered_set<int> num1_set(nums1.begin(),nums1.end()); //将nums1的值begin到end赋值给num1——set for (int num : nums2) { if (num1_set.find(num) != nullptr) { //利用stl中的find result_set.insert(num); } } return vector<int>(result_set.begin(),result_set.end()); } };