深信服笔试，给出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

相关推荐

11-23 12:12
华东师范大学 FAE
点赞 评论 收藏
分享
11-24 17:16
已编辑
华中科技大学 C++
英伟达 C++开发 一面
聊天：你现在在实习，基于什么考虑要离职找新的实习？对这个职位有多少了解？面试官介绍岗位工作内容。C++:virtual关键字作用？构造函数可以是虚函数吗？析构函数可以是虚函数吗？virtual除了可以用于虚函数，还可以用于继承时放在基类前，了解吗？c++类，有些函数是默认生成的，比如构造函数，还有？new、delete构造和析构一个类，那么如果我要构造一组对象？stl，常用的有哪些？stack使用场景？深度还是广度搜索？static_cast和dynamic_cast区别？图形：OpenGL 渲染管线？前向渲染和延迟渲染？多边形反走样？纹理，有哪些常见的采样或者说过滤方式？调用系统函数和调用自...
查看18道真题和解析
点赞 评论 收藏
分享
10-31 19:24
门头沟学院 硬件开发
大疆寄
太丑陋了。
耀孝女：就是你排序挂了
点赞 评论 收藏
分享
11-15 13:21
广西科技师范学院 软件测试
初筛都过不了，求指教
尊嘟假嘟点击就送：加v细说，问题很大
点赞 评论 收藏
分享
11-25 10:05
北京理工大学 其他汽车制造职位
点赞 评论 收藏
分享
评论
点赞
6
分享

招聘动态

查看更多

阿里云管培生

2025届校园招聘

快手Star

2025届招聘

快手

销售类投递专区

富士通（西安）

2025校园招聘

全站热榜

正在热议
# 拼多多求职进展汇总 #
233494次浏览 2032人参与
# 在职场上，你最讨厌什么样的同事 #
5760次浏览 81人参与
# 阿里云管培生offer #
59170次浏览 1748人参与
# 25届秋招总结 #
397241次浏览 3983人参与
# 哪些公司校招卡第一学历 #
32888次浏览 105人参与
# 地方国企笔面经互助 #
6569次浏览 16人参与
# 北方华创开奖 #
66046次浏览 549人参与
# ai智能作图 #
21610次浏览 262人参与
# 硬件兄弟们 甩出你的华为奖状 #
77972次浏览 625人参与
# 实习，投递多份简历没人回复怎么办 #
2436155次浏览 34704人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
4740次浏览 47人参与
# 实习与准备秋招该如何平衡 #
722927次浏览 8551人参与
# 我的实习求职记录 #
6122581次浏览 83956人参与
# 如果再来一次，你还会选择这个工作吗？ #
110753次浏览 1114人参与
# 25届机械人为了秋招做了哪些准备？ #
25075次浏览 356人参与
# 签了三方后想毁约怎么办 #
18569次浏览 111人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
9977次浏览 215人参与
# 机械求职避坑tips #
22249次浏览 241人参与
# 游戏求职进展汇总 #
52816次浏览 344人参与
# 夸夸我的求职搭子 #
132046次浏览 1360人参与
# 腾讯求职进展汇总 #
207648次浏览 1694人参与
# 实习想申请秋招offer，能不能argue薪资 #
35800次浏览 308人参与
牛客网
牛客企业服务