算法题每日一练---第58天:错误的集合

简介: 集合 s 包含从 1 到 n 的整数。

3.png

一、问题描述


集合 s 包含从 1n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。


题目链接:错误的集合


二、题目要求


样例

输入: nums = [1,2,2,4]
输出: [2,3]


考察

哈希表(map)
建议用时10~25min


三、问题分析


本题是位运算的第13题,没了解过位运算相关知识点可以看这一篇文章,讲解比较详细:

算法题每日一练---第45天:位运算


这一题,一开始我打算向位运算的异或靠拢的,将1~n下标数字与数组元素进行异或,那么最后只剩下一个缺失的下标、一个重复的数组元素。但后来发现不行,异或不能同时保留这两个数字。

13.png

我又试着搞一下map计数,因为重复数字的哈希值肯定为2,缺失数字的哈希值肯定为1,最后判断一下就行了。


除了这种,还可以排序之后彼此相邻的数字判断是否重复,也可以。


四、编码实现


classSolution {
public:
vector<int>findErrorNums(vector<int>&nums) {
vector<int>v;//数组存储inti,n=nums.size(),a,b;//初始化变量map<int,int>m;
for(i=0;i<n;i++)//计数        {
m[nums[i]]++;
        }
for(i=1;i<=n;i++)//判断数字        {
if(m[i]==2)//重复数字a=i;
if(m[i]==0)//丢失数字b=i;
        }
v.push_back(a);//插入数字v.push_back(b);//插入数字returnv;//输出结果    }
};

五、测试结果14.png

目录
打赏
0
0
2
0
282
分享
相关文章
ArrayList集合的两个实例应用,有趣的洗牌算法与杨辉三角
ArrayList集合的两个实例应用,有趣的洗牌算法与杨辉三角
89 1
带用集合算法set union讲解
带用集合算法set union讲解
133 0
【Python深入学习】- 书籍推荐|数据结构和算法介绍|内建集合数据类型
【Python深入学习】- 书籍推荐|数据结构和算法介绍|内建集合数据类型
127 1
92 C++ - 常用集合算法
92 C++ - 常用集合算法
95 0
【算法每日一练及解题思路】有n级台阶,一次只能上1级或2级,共有多少种走法?
本文深入解析了“爬楼梯问题”,探讨了递归与迭代两种解法,并提供了Java代码实现。通过分析问题本质,帮助读者理解动态规划技巧,提高解决实际编程问题的能力。关键词:Java, 算法, 动态规划, 爬楼梯问题, 递归, 迭代。
382 0
突击面试:解密面试官的算法题集合
突击面试:解密面试官的算法题集合
Java数据结构与算法:用于处理不相交集合的合并和查找问题
Java数据结构与算法:用于处理不相交集合的合并和查找问题

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问