Hash Table O(1) 记录一切
1.哈希表的这个结构的使用, 核心目标是期望通过记录一些已经存在的值, 然后就能实现 O(1) 的检索
2.处理实际问题时, 要想清楚我们要设计怎样的 key, 有没有更简单且不碰撞的记录方法
169.多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例 1：输入：nums = [3,2,3] 输出：3
示例 2：输入：nums = [2,2,1,1,1,2,2] 输出：2
分析:
1.多数元素一定是出现次数最多的那个元素, 扫一遍记录每个元素出现的次数, 扫的时候维护出现次数最大的那个元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> num2cnt;
int ans = nums[0];
int maxCnt = 1;
for (auto x: nums) {
num2cnt[x] += 1;
if (num2cnt[x] > maxCnt) {
ans = x;
maxCnt = num2cnt[x];
}
}
return ans;
}
};
41.缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：输入：nums = [1,2,0] 输出：3
示例 2：输入：nums = [3,4,-1,1] 输出：2
示例 3：输入：nums = [7,8,9,11,12] 输出：1
分析:
1.题目要求 O(n) 时间 和 O(1) 空间; 如果没有限制这个我们估计怎么做, 遍历放哈希表, 然后从1开始枚举看哪个不存在在哈希表, 但是会引入到 O(n) 空间
2.这个题目需要引入一种原地哈希的思路, 在原始的数组中修改, 这样才能不引入额外的空间
3.对于一个长度为 N 的数组, 未出现的最小正数的范围在 [1, N+1], 如果 [1,N] 都出现了, 那么第一个没出现的正数就是 N+1; 否则就是在 [1, N] 中没有出现的最小正整数; 所以我们想对 [1, N] 范围的数放入哈希表
4.怎么把 [1, N] 范围的数放入哈希表, 但是有不建立新的哈希表呢? 放在原始的数组里面: 我们对数组进行遍历, 对于遍历到的数字 x, 如果它在 [1, N] 范围内, 那么就将 x - 1 这个[位置] 打上 [某种标记], 因此遍历结束之后, 如果所有 [位置] 都有标记, 那么缺失的就是 N+1 这个数字; 否则就是没有打上标记的的位置 + 1 这个数字就是第一个缺失的正数
5.举个例子, 数组长度是 5, 我们对于数字 1, 我们对 0 位置上打标记, 全打完所有标记之后, 没打上标记的位置就是 + 1, 就是缺失的数字: 比如我们发现, 我们在 2 位置没有标记, 那么就说明 3 这个数字缺失了
6.到此为止, 我们只需要设计某种标记的规则, 就能完成上面的操作; 对于负数, 这种不在我们考虑的范围内, 只需要排除它对我们后续的干扰就行, 这里一种设计方法是打一个较大的正数 N + 2, 这样数组里面的数字就都是正数了, 遍历数字的时候, 如果绝对值 超出 N 的一律不考虑
7.我们可以将 [标记] 的产生, 设置成 打了[负号] 的 [负数], 也称为 [负数标记]; 比如一个数字 3, 我们让它在 nums[2] 位置上的负数 -nums[2]
8.举个完整的例子:
3,4,-1, 1, 9,-5 第一步, n = 6 将负数替换成 n + 2 = 8
3,4, 8, 1, 9, 8 第二步, 做完上一步所有数字都是正数了, 对所有不大于 6 的数字, 标记为负数, 标记的方法是 nums[num - 1] = - 原始数字的绝对值
-3,4,-8,-1, 9, 8 第三步, 做完上一步已经标记好正数了, 如果现在还有正数就是缺失的那个数字, 缺失数字对应的是 i + 1
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int len = nums.size();
// 把负数都标记成 len + 2, 至少是标记为 len + 1
for (int& x: nums) {
if (x <= 0) {
x = len + 2;
}
}
for (int i = 0; i < len; ++i) {
int num = abs(nums[i]); // 先取出来绝对值, 用于下面判断这个数之前不是负数
// 对这些需要考虑的正数 (之前的负数不需要再考虑), 也就是 num <= len 的数, 搞上 [负数标记]
if (num <= len) {
nums[num - 1] = -abs(nums[num - 1]); // 打上负数标记, 直接对这个数字取一个负数;
}
}
// 遍历已经打好标记的结果, 找第1个剩下的正数, 找到了, 那么就返回 i + 1
// 第一个大于 0 的数 index + 1 就是缺失正数
for (int i = 0; i < len; ++i) {
if (nums[i] > 0) {
return i + 1;
}
}
// 如果找不到, 那么第1个确实的正数就是 len + 1
return len + 1;
}
};
49.字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。
示例 1: 输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2: 输入: strs = [“”] 输出: [[“”]]
示例 3: 输入: strs = [“a”] 输出: [[“a”]]
分析:
1.按照每一类异位词进行分组哈希, 然后遍历哈希表, 哈希函数设计成什么呢?
2.一种简单的做法是 26 个字符出现的次数拼起来的字符串, 对于 abd 来说就是 “11010000..00” 这样, 但是一个词出现的次数大于 10 次造成冲突, 所以在每个位置之间增加一个分隔符, 比如 1#1#0#1..#0#
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> ans;
unordered_map<string, vector<string>> group2strs;
auto hash = [] (string s) {
vector<int> cnt(26, 0);
for (char c: s) {
cnt[c - 'a'] += 1;
}
string hashStr = "";
for (auto c: cnt) {
hashStr += to_string(c) + "#";
}
return hashStr;
};
for (auto s: strs) {
group2strs[hash(s)].push_back(s);
}
for (auto x: group2strs) {
ans.push_back(x.second);
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
