《LeetCode》—— 哈希

今天刷题讲解的主要讲的是关于——哈希这个知识点的题目讲解。

（一）缺失的第一个正整数

（二）数组中只出现一次的两个数字

1、直接法

2、哈希

（三）直线上最多的点数

（一）缺失的第一个正整数

链接如下：缺失的第一个正整数

题目展示：

题意分析：

分析题目，我们知道以下几点：

1、如果数组中有负数，对于负数的处理我们是忽略的，即只判断正数情况下缺失的第一个正整数；

2、对于长度为n的数组，并且无重复出现的数字，那么如果遍历数组之后，此时会有两种情况：

①如果数组中的元素出现了1~n之间的，那么我们就可以知道缺失的就是 n+1 这个数字；
②相反，如果数组中的元素在 1~n 之间有缺失的，那么缺失数字就处于1～n 中的数字。如果是这种情况。我们只需利用哈希表判断出每个元素是否出现过即可。

具体做法：

step 1：首先就是需要创建一个哈希表，用于记录数组中出现的数字。
step 2：从头开始遍历数组，记录数组中数字出现的次数；
step 3：紧接着查询哈希表中是否有这个数字，如果没有，说明它就是数组缺失的第一个正整数

代码展示：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {unordered_map<int, int> tmp;for (auto& e : nums) {if (e > 0) tmp[e]++;}for (int i = 1; i <= nums.size() + 1; i++) {if (tmp[i] == 0) return i;}return 0;}
};

性能分析：

时间复杂度：O(n)。第一次遍历数组，记录数字出现次数为O(n)，第二次最坏从1遍历到n，为O(n)，因此时间复杂度为 O(n)。
空间复杂度：O(n)。哈希表记录n个不重复的元素，长度为n，因此空间复杂度为 O(n)。

（二）数组中只出现一次的两个数字

链接如下：数组中只出现一次的两个数字

题目展示：

题意分析：

首先，本题的题意还是比较简单的。对于本题我们既可以使用哈希，也可以不使用哈希，这两种方法都可以作出本道题。接下来，我两种方法都给大家介绍一下。

1、直接法

具体思想：

直接去做，其实思想也很简单。首先，我们可以先对数组进行排序处理，这是非常关键的一步；
其次，对于排好序的数组，我们可以知道，对于相同的数字一定是挨在一起的，因此，我们可以利用这一点去对其进行判断。

具体做法：

step 1：首先就是对数组中的元素进行排序处理；
step 2：从头开始遍历数组，查找出连续挨着的两个数字是不同的即可；
step 3：如果连续两个挨着的数字是相同的，那么我们只需从当前位置往后跳两个位置继续查找即可

代码展示：

class Solution {
public:vector<int> FindNumsAppearOnce(vector<int>& array) {// write code heresort(array.begin(),array.end());vector<int>tmp;int size=array.size();for(int i=0; i<size;++i ){if(array[i] == array[i+1])i++;elsetmp.push_back(array[i]);}return tmp;}
};

2、哈希

具体思想：

既然有两个数字只出现了一次，我们就统计每个数字的出现次数，利用哈希表的快速根据key值访问其频率值即可实现题目要求。

具体做法：

step 1：首先还是对数组中的元素进行排序处理；
step 2：从头开始遍历数组，用哈希表统计每个数字出现的频率；
step 3：然后再遍历一次数组，对比哈希表，找到出现频率为1的两个数字，返回即可实现

代码展示：

class Solution {
public:vector<int> FindNumsAppearOnce(vector<int>& array) {// write code heresort(array.begin(), array.end());unordered_map<int, int> tmp;vector<int> res;for(auto& e : array)++tmp[e];//再次遍历数组for(int i = 0; i < array.size(); i++){//找到频率为1的两个数if(tmp[array[i]] == 1)res.push_back(array[i]);}return res;}
};

性能分析：

时间复杂度：O(n)，其中n为数组长度，两次单独的遍历数组每个元素
空间复杂度：O(n)，哈希表的长度应该为(n−2)/2

（三）直线上最多的点数

链接如下：149. 直线上最多的点数

题目展示：

题意分析：

本题暴力的解决就是任意举两个点来枚举直线，但是它的时间复杂度达到了O(N^3)，所以这里就不过多的介绍；

那么我们可以怎么优化呢？我们以下图为例带大家理解思路：

注意：

在计算斜率时如果换成浮点则会有精度的问题，因此我们换成分数来进行操作

具体做法：

step 1：在点的总数量小于等于 2 的情况下，我们只需用一条直线将所有点串联，此时我们直接返回点的总数量即可；
step 2：从头开始遍历数组，枚举中心点；
step 3：紧接着通过中心点去算出与其他点的斜率斜率，计算出最多的个数。在重复上述操作即可实现；

代码展示：

class Solution {
public:int maxPoints(vector<vector<int>>& points) {int n = points.size();//当结点数小于2时，直接返回即可if (n < 2) return n;int ans = 0;//枚举中心店for (int i = 0; i < n; i++) {//定义哈希表来统计每个斜率的数量unordered_map<string, int> tmp;//定义Count用来来表示最大的数量int Count = 0;//枚举剩余点，因为i之前的已经枚举过了，所以才 i+1开始for (int j = i + 1; j < n; j++) {//获取两点的坐标int x1 = points[i][0] ,y1 = points[i][1];int x2 = points[j][0] ,y2 = points[j][1];//计算斜率string key = clac(x1,x2,y1,y2);tmp[key]++;//更新CountCount = max(Count, tmp[key]);}//一个中心点完成后更新结果ans = max(ans, Count+1);}return ans;}string clac(int x1, int x2, int y1, int y2){//计算横纵坐标的差值，注意记得加绝对值int index=abs(x1-x2);int indey=abs(y1-y2);//最大公约数int val=gcd(index, indey);//拼接string key=to_string (indey / val) + "_" + to_string (index / val);//斜率为负，拼接一个 -号if((x1 < x2 && y1 > y2) || (x1 > x2 && y1 < y2))return "-" + key;return key;}
};

性能分析：