《LeetCode》—— 哈希

简介: 《LeetCode》—— 哈希

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


(一)缺失的第一个正整数

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

题目展示:

题意分析:

分析题目,我们知道以下几点:

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、直接法

具体思想:

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

具体做法:

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

代码展示:

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        sort(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++;
            else
                tmp.push_back(array[i]);
        }
        return tmp;
    }
};

2、哈希

具体思想:

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

具体做法:

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

代码展示:

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        sort(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]++;
                //更新Count
                Count = 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;
    }
};

性能分析:

  • 时间复杂度:O(n^2*logn),其中n为数组长度,枚举中心点需要O(N),而斜率分组也需要O(N),对于最大公约数需要O(logN),因此时间复杂度为O(n^2logn)
  • 空间复杂度:O(n),因为需要哈希表来记录,因此空间复杂度为O(N)。

到此,关于哈希表的三道题就讲解结束了。希望对大家有帮助,咱们下期再见!!!

相关文章
|
6月前
leetcode-1044:最长重复子串(滚动哈希)
leetcode-1044:最长重复子串(滚动哈希)
133 0
|
5月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
5月前
|
存储 SQL 算法
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
LeetCode 题目 87:递归\动态规划\哈希实现 扰乱字符串
|
6月前
[leetcode] 705. 设计哈希集合
[leetcode] 705. 设计哈希集合
|
6月前
leetcode-1001:网格照明(自定义哈希集合)
leetcode-1001:网格照明(自定义哈希集合)
42 0
|
算法 索引
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
如果我们用前缀 prefix 和 后缀 suff去暴力对比所有单词肯定会超时,我们可以先把单词里所有的前缀后缀组合,中间用特殊符号@连接,对应的最大下标存入哈希表中。搜索时,用特殊符号@连接前缀后缀,在哈希表中进行搜索
97 0
leetcode-每日一题745. 前缀和后缀搜索(哈希和字典树)
|
算法
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
题目要求斐波那契数列长度要大于等于3,就等于说要确定 x[1] 和 x[2]来确定x[3]…x[n]之和的数列,所以我们用两层for循环来枚举x[1] 和 x[2] ,因为斐波那契数列满足 x[i] = x[i - 1] + x[i - 2], 所以x[3] = x[1] + x[2] x[4] = x[3] + x[2]…,我们只需要三个变量来不断变换, 每次从 arr 中找前两个数,然后查看后续在符合斐波那契的数在arr中是否存在
106 0
leetcode-每日一题873. 最长的斐波那契子序列的长度(哈希和二分)
|
算法
leetcode-每日一题648. 单词替换(哈希)
将字符串数组中的所有字符串存入哈希表中,遍历sentence中的所有单词,从短到长遍历单词前缀,对比哈希表中的单词是否存在,存在则替换。
76 0
leetcode-每日一题648. 单词替换(哈希)
|
算法 容器
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】
对应力扣.17电话号码的字母组合,详细动画和图示讲解,带你快乐刷题
91 0
力扣17 - 电话号码的字母组合【回溯、哈希映射、队列】