深信服笔试,给出n个数和n-1个数找出少了哪个数,怎么用哈希

昨天做的一道深信服的编程题。给出n个数和n-1个数,要求找出少了哪个数。顺序会被打乱,要求时间复杂度为O(n)。
当时是准备用空间换时间,用一个超大的bool数组,使n-1个数对应的数组位置为真,再对n个数遍历对应boo数组的位置,为假的就是少的。后来同学一跟我说用hash才恍然大悟,但是我没有用过C++里面的hashmap,这个要怎么用啊,请教一下。(出来才查到求和再相减)。。
#深信服#
全部评论
异或更简单
点赞 回复 分享
发布于 2019-03-10 16:17
面试官让我用数学方法重写做一下,我说重新加起来再减下去不会溢出吗...
点赞 回复 分享
发布于 2019-03-10 16:24
异或是正确答案。。
点赞 回复 分享
发布于 2019-03-10 16:28
hashmap不太可能o(n)吧
点赞 回复 分享
发布于 2019-03-10 16:41
异或 n^m^n=m m就是少的那个数
点赞 回复 分享
发布于 2019-03-10 18:03
将多的数加入map。存储出现的次数。少点那个数组去get。然后移除。剩的就是多的
点赞 回复 分享
发布于 2019-03-10 19:19

相关推荐

一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
牛客410815733号:这是什么电影查看图片
点赞 评论 收藏
分享
评论
点赞
6
分享
牛客网
牛客企业服务