必刷算法题之哈希篇(题目及代码)---C++

这篇具有很好参考价值的文章主要介绍了必刷算法题之哈希篇(题目及代码)---C++。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第一题:两数之和

必刷算法题之哈希篇(题目及代码)---C++
解法1:(对于大规模数据,时间和空间复杂度会超出)
解题思路如下:
假设第一个数为a,用目标值c减去第一个数a,得到b,然后遍历后面的数,查看b是否在后面的数组中

class Solution {
public:
    /**
     
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        int a,b;
        vector<int> res;
        for(int i=0;i<numbers.size();i++){
            a=numbers[i];
            b=target-a;
            for(int j=i+1;j<numbers.size();j++){
                if(b==numbers[j]){
                    res.push_back(i+1);
                    res.push_back(j+1);
                    return res;
                }
            }
        }
        return res;
    }
};

解法2:(利用哈希表)

class Solution {
public:
    /**
     * 
     利用哈希表
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        int n = numbers.size(); 
        vector <int> res;
        if (!n)   //为空的话,直接返回
            return res;
        // 定义哈希表,unordered_map是用哈希表实现的,复杂度为O(1),而map是用红黑树实现的
        unordered_map<int, int> hashmap;   //第一个int表示值,第二个int表示下标

        for (int i = 0; i < n; i ++) {
            if ( hashmap.end() != hashmap.find(target - numbers[i]) ) { // find函数如果没有找到,会返回hashmap.end()
                // 将结果存入数组
                res.push_back(hashmap[target - numbers[i]] + 1); 
                res.push_back(i + 1);
                break;
            } else {
                hashmap[numbers[i]] = i; // 将未找到的值插入哈希表中,继续遍历
            }
        }
        return res;
    }
};

第二题: 数组中出现次数超过一半的数字

必刷算法题之哈希篇(题目及代码)---C++

解法1:(排序)
由于多数元素是指在数组中出现次数大于 【n/2】 的元素,那么将数组排序后,即便该元素是最小元素或是最大元素,其在数组中的覆盖范围也超过了数组中点(从左到右超过或是从右到左超过)。于是得到算法:

  • 将数组排序;
  • 返回数组中点元素nums[nums.size()/2] .
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    sort(numbers.begin(),numbers.end());
    return numbers[numbers.size()/2];
    }
};

是不是觉得很简单,多加两行代码就能搞定。(但是时间复杂度还是慢了)
时间复杂度: O(mlogm)。m为数组元素数,主要是排序的时间消耗。
空间复杂度: O(logm)。主要是系统sort函数需要的栈空间消耗。

解法2: (哈希)
如果考虑使用哈希表空间换时间,则可以降低时间复杂度。我们可以使用哈希表存储数组中元素出现的次数,当某个元素的出现次数超过一半时,返回该元素。于是得到算法:

  • 1.初始化存储数组元素及其出现次数的哈希表map1,键为元素值,值为该元素在数组中的出现次数;
  • 2.遍历数组元素,将被遍历数组元素的哈希值加一;
  • 3.若该元素在数组中的出现次数超过数组元素数的一半,返回该元素。
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
    unordered_map<int, int> map1;  //存储数组元素值及出现次数的哈希表
    for(int i=0;i<numbers.size();i++){  //遍历数组元素
        map1[numbers[i]]++;
        if(map1[numbers[i]]>(numbers.size()/2)){  //若该元素出现此处超过一半
            return numbers[i];
        }
    }    
    return 0;//为了能通过编译
    }
};

解法3:(摩尔投票法)
该方法是网上看到的,觉得很有意思。
场景描述
考虑这样一个场景,一群人打擂台,人群中分为不同的帮派,挨个上台比武。留在台上的帮派为擂主帮派,如果上台的人不是自己帮派的人,则将其干掉,代价是损失一个帮派成员;如果上台的人是自己帮派的人,则将其留下。则当所有人都参与完比武后,留在台上的必然是人数最多的帮派。
而在本题中,多数元素出现次数超过数组元素数的一半,也即,其他所有元素加起来都没多数元素多。如果我们记多数元素的值为1,其他元素的值为0,将数组中所有元素值相加,结果必然大于0。于是我们可以设计这样一种算法:

  • 1.初始化候选答案ans为nums[0],初始化数值计算结果count为0;
  • 2.遍历数组若该元素与备选答案相等,count加一,否则减一;
  • 3.若count减为零,更换备选答案ans为当前元素,重置count为1,继续遍历后续元素。遍历完成后返回最终的ans即为多数元素。
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0];//初始化候选答案为nums[0]
        int count = 0;//初始化数值计算结果为0
        for(auto num : nums){//遍历数组
            if(num==ans) ++count;//若该元素与备选答案相同,则count加一
            else{//否则减一
                --count;
                if(count==0){//若count减为0
                    ans = num;//更换备选答案为当前元素
                    ++count;//重置count为1
                }
            }
        }
        return ans;//返回答案
    }
};

第三题: 数组中只出现一次的两个数字

必刷算法题之哈希篇(题目及代码)---C++
这道题其实和第二题很类似,因此有差不多的解法,解题思路如下:

  • 定义一个哈希表<int,int>,第一个数表示值,第二个数表示出现的次数,利用for循环遍历array,然后找出第二个int为1的两个数
  • 直接返回这两个数
class Solution {
public:
    /**
    思路:
    step1:定义一个哈希表<int,int>,第一个数表示值,第二个数表示出现的次数,利用for循环遍历array,然后找出第二个int为1的两个数
    step2:直接返回这两个数
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        unordered_map<int, int> map1;  //存储数组元素值及出现次数的哈希表
        vector<int> a;
        for(int i=0;i<array.size();i++){
            map1[array[i]]++;
        }
        for(int i=0;i<array.size();i++){
            if(map1[array[i]]<2){
                a.push_back(array[i]);
            }
        }
        sort(a.begin(),a.end());  //题目要求输出的结果按照非降序排列
        return a;
    }
};

第四题:缺失的第一个正整数

必刷算法题之哈希篇(题目及代码)---C++
数组nums的长度为n,所以正整数的范围为【1,n+1】,因此缺失的第一个正整数要么在 [1,n] 中,要么是n+1
解法1: 哈希

  • 首先遍历整个数组,并用unordered_map标记该数字已出现
  • 然后从1遍历到n,并在unordered_map查找该值是否出现,未出现则直接返回
  • 若长度为n的数组里n个数字都出现了,则第n+1个数字一个未出现
class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
    	int n=nums.size();
    	unordered_map<int,int>m;
        for(int i=0;i<n;i++){//统计每个数字出现的次数
        	m[nums[i]]++;
		} 
        for(int i=1;i<=n;i++){//出现次数为0的直接返回
        	if(m[i]==0)return i;
		}
		return n+1;  //运行到这一步,说明确实的数为n+1
    }
};

时间复杂度和空间复杂度分析:

  • 时间复杂度:O(n),遍历了一次长度为n的数组和枚举一次长度n-1的数
  • 空间复杂度:O(n),建立了长度为n的哈希表

解法2: 排序后直接遍历

  • 对输入的数组进行排序
  • 遍历一次数组,不是正整数的数则统计其个数,是正整数则按序从1开始往后逐次比较,比较不成功的则直接返回
  • 最后若能遍历完数组,说明这是一串从1开始连续的数组,则返回n+1即可
class Solution {
public:
    int minNumberDisappeared(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size(),cn=0,cn2=0;
        for(int i=0;i<n;i++){
            if(nums[i]<=0)cn++;//不是正整数的数则统计其个数
            else if(nums[i]!=++cn2)return cn2;//是正整数则按序从1开始往后逐次比较,比较不成功的则直接返回
        }
        return n-cn+1;
    }
};

eg1: 排序后的数组为[-2,-1,0,1,3,4],这个例子会执行到i=4即3这个位置就停下,因为3!=2,return cn2=2;
eg2: 排序后的数组为[1,2,3,4,5],for循环会执行完毕,且cn==0,return 5-0+1即return 6.

第五题:三数之和

必刷算法题之哈希篇(题目及代码)---C++
解法1: 暴力搜索
时间复杂度: O(nlogn) +O(n^3);排序算法O(nlogn)+三重循环枚举

空间复杂度: O(n);数组存储与读取数据

 class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>>ans;
        if(num.size()<3)return ans;
        sort(num.begin(),num.end());//排序使最后结果满足非降序排列
        for(int i=0;i<num.size()-2;i++){
        //注意细节:如果循环的当前数和之前一样,则continue
        //即如果数组中出现了先前已经找过的重复数字,则不必再找了
            if(i&&num[i]==num[i-1])continue;  //其实这里还不算完整,因为可能会出现隔几个数相同的情况。
            for(int j=i+1;j<num.size();j++){  //不重复选择当前数加1
                if(j>i+1&&num[j]==num[j-1])continue;
                for(int k=j+1;k<num.size();k++){
                    if(k>j+1&&num[k]==num[k-1])continue;
                    if(num[i]+num[j]+num[k]==0){
                        ans.push_back({num[i],num[j],num[k]});//最后输入按非降序排列
                    }
                }
            }
        }
        return ans;
    }
};

解法2: 双指针优化(该方法来自牛客网精华题解,非常值得学习)

具体思路:

  • 首先对输入的数据的大小进行判断,如果数小于3个,那么直接返回空。
  • 对输入的数据进行排序,注意排完序后第一个数肯定是负数,除非是0、0、0这种情况的
  • for循环选择第一个数x,然后创建两个指针i和j,指针i指向x的下一个数,指针j指向最后一个数。
  • 因为x肯定小于0,所以若指针i 加指针j 大于当前数x的相反数,则指针j --;若指针i 加指针j 小于当前数x的相反数,则指针i++;若指针i 加指针j 等于当前数x的相反数,则答案为x 和指针i 与j 的三元组。
  • 若x>0,那么return 空;

时间复杂度: O(nlogn) + O(n^2);排序算法O(nlogn)+双指针

空间复杂度: O(n);数组存储与读取数据

下图演示了双指针算法过程:必刷算法题之哈希篇(题目及代码)---C++
具体代码如下:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>>ans;
        if(num.size()<3)return ans;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size()-2;i++){
            if(num[i]==num[i-1]&&i)continue;
            int l=i+1,r=num.size()-1;
            while(l<r){
                if(num[l]+num[r]==-num[i]){//若指针i 加指针j 等于当前数x 则答案为x 和指针i 与j 的三元组。

                    ans.push_back({num[i],num[l],num[r]});  //可以同时插入三个数
                    while(num[l]==num[l+1]&&l+1<r)l++;  //如果后面的数和前面的一样,那么忽略掉
                    while(num[r]==num[r-1]&&r-1>l)r--;
                    l++,r--;  //指针继续移动,查看后面还有没有组合
                }
                else if(num[l]+num[r]>-num[i]){//若指针l 加指针r 大于当前数-num[i]则指针r --,
                    r--;
                }
                else l++;//若指针l 加指针r 小于当前数-num[i]则指针l++,
            }
        }
        return ans;
    }
};

注: 以上题目都是在牛客网的剑指offer题库中刷的,有自己做的,也有不会做看别人精华解题思路,然后总结的。如果侵犯了您的权益,请私聊我。
最后,觉得本文内容对你有所帮助的话,感谢点赞收藏,在我的剑指offer专栏还有相关的算法刷题文章,等待您的阅读!

导航链接:必刷算法题—二分查找(C++)
导航链接:必刷算法题—排序篇(C++)
导航链接:剑指—树篇(C++)
导航链接:剑指—动态规划篇(C++)
导航链接:剑指—链表篇(C++)
导航链接:剑指—队列&栈篇(C++)文章来源地址https://www.toymoban.com/news/detail-417352.html

到了这里,关于必刷算法题之哈希篇(题目及代码)---C++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法入门必刷】数据结构-栈(一)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月13日
    浏览(93)
  • 哈希表题目:原子的数量

    标题:原子的数量 出处:726. 原子的数量 8 级 要求 给你一个表示化学式的字符串 formula texttt{formula} formula ,返回每种原子的数量。 原子总是以一个大写字母开始,跟随零个或任意个小写字母,表示原子的名字。 如果数量大于 1 texttt{1} 1 ,原子后会跟着数字表示原子的数量

    2024年02月06日
    浏览(33)
  • 哈希表题目:LFU 缓存

    标题:LFU 缓存 出处:460. LFU 缓存 9 级 要求 请你为 最不经常使用(LFU)缓存 设计并实现数据结构。 实现 LFUCache texttt{LFUCache} LFUCache 类: LFUCache(int   capacity) texttt{LFUCache(int capacity)} LFUCache(int capacity) 用数据结构的容量 capacity texttt{capacity} capacity 初始化对象。 int   get(int  

    2024年02月07日
    浏览(33)
  • 哈希表题目:设计推特

    标题:设计推特 出处:355. 设计推特 7 级 要求 设计一个简化版的推特,可以让用户实现发送推文,关注/取消关注其他用户,能够看见关注人(包括自己)的最近 10 texttt{10} 10 条推文。 实现 Twitter texttt{Twitter} Twitter 类: Twitter() texttt{Twitter()} Twitter() 初始化简易版推特对象。

    2024年02月05日
    浏览(50)
  • leetcode 哈希表相关题目

    题目:https://leetcode.cn/problems/valid-anagram/description/ 题解:https://leetcode.cn/problems/valid-anagram/solutions/2602947/shu-zu-ha-xi-biao-tong-ji-mei-ge-zi-mu-c-vhh5/ 题目:https://leetcode.cn/problems/intersection-of-two-arrays/description/ 题解:https://leetcode.cn/problems/intersection-of-two-arrays/solutions/2603171/jie-guo-shu-zu-un

    2024年01月21日
    浏览(38)
  • 哈希表C++哈希表详解(知识点+相关LeetCode题目)

    目录 前言 一、什么是哈希表 二、哈希表的操作 2.1 操作时间复杂度 2.2 哈希表通用API 2.3 建立哈希表 2.3 哈希表常见结构介绍 Set(集合) Map(映射) unordered_map(哈希表) 三、哈希表的力扣经典题目 有效的字母异位词242 两个数组的交集 349 两数之和1 四数相加II 454 三数之和

    2024年03月20日
    浏览(46)
  • 哈希表题目:TinyURL 的加密与解密

    标题:TinyURL 的加密与解密 出处:535. TinyURL 的加密与解密 7 级 要求 TinyURL 是一种 URL 简化服务。当你输入一个 URL,例如 https://leetcode.com/problems/design-tinyurl 时,它将返回一个简化的 URL,例如 http://tinyurl.com/4e9iAk 。设计一个类对 URL 加密和对 TinyURL 解密。 你的加密和解密算法如

    2024年02月04日
    浏览(33)
  • 全面理解哈希,哈希的底层原理是如何实现的,哈希题型的做题思路与题目清单(不断更新)

    哈希(Hash)是一种算法,它接受一个输入(或“消息”),并返回一个固定大小的字符串。这个输出字符串的大小通常以字节为单位,输出的内容看起来是随机的且整个过程是单向的。 哈希的一些关键特性包括: 不管你输入的信息有多大,哈希值的大小总是固定的。 即使只

    2024年02月04日
    浏览(43)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(一)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月03日
    浏览(63)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(四)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月02日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包