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

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

相关推荐

12-19 20:33
蓝禾技术_电商事业部_电商运营管培生(准入职员工)
蓝禾科技内推，蓝禾科技内推码
面经：蓝禾的流程推得很快，基本上投完两天就接到了hr的初试电话，直接进行了初试。初试全程大概三十分钟，hr小哥态度很和善。主要问了实践经历获奖的情况最有成就感的事情对电商运营的理解选择公司的标准等，都是比较常规的问题。禾你一起，做不可能的事 | 蓝禾26届校招启动啦公司介绍：蓝禾2008年成立于深圳，是一家集产品、设计、研发、品牌、营销、大数据运营于一体的创新型科技公司，旗下拥有图拉斯TORRAS、锐舞RANVOO、卡斯酷CASEKOO等多个品牌招聘岗位：运营(国内)、运营(国外)、营销、设计、研发技术、职能工作地点：深圳内推链接：https://lanhevip.jobs.feishu.cn...
点赞 评论 收藏
分享
今天 10:34
门头沟学院 C++
点赞 评论 收藏
分享
12-02 17:34
阿里云_基础平台研发_云计算(准入职员工)
点赞 评论 收藏
分享
12-19 20:51
vivo_数据算法工程师(准入职员工)
正浩创新内推，正浩创新内推码
26届女硬件工程师丨正浩创新面经及流程9.1一面1.自我介绍2.有无相关电源设计项目或经历，并浅谈3.DCDC拓扑手撕（但是我当时没带纸笔所以口头描述），BUCK和BOOST，同步异步的区别和优缺点，同步电路的控制方式（施加什么PWM波形，如何控制MOS通断）4.项目中最有挑战性的部分，怎么解决的，然后会深挖这一部分再提问（这个问题出现的根本原因，下次如何避免）5.面试官说我专业其实不是很对口，不是电气工程专业，所以问的比较浅，大家仅供参考9.2收到笔试链接，非笔试，为性格测试9.5收到二面短信9.8 二面，没有技术问题，主要问了在校做过什么项目，调试遇到什么问题，除此之外有没有做过电源相关项...
点赞 评论 收藏
分享
评论
点赞
6
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 2025年终总结 #
167438次浏览 2825人参与
# 找工作，行业重要还是岗位重要？ #
84854次浏览 1679人参与
# 你面试体验感最差/最好的公司 #
13692次浏览 221人参与
# 一人说一个提前实习的好处 #
8433次浏览 173人参与
# 今年你最想重开的一场面试是？ #
2875次浏览 56人参与
# 秋招落幕，你是He or Be #
8073次浏览 174人参与
# 重来一次，你会对开始求职的自己说 #
5310次浏览 134人参与
# 实习没事做是福还是祸？ #
13884次浏览 216人参与
# 职场上哪些行为很加分？ #
305590次浏览 3438人参与
# 大家每天通勤多久？ #
68591次浏览 430人参与
# 团建是“福利”还是是 “渡劫” #
6304次浏览 141人参与
# 你小心翼翼的闯过多大的祸？ #
10333次浏览 148人参与
# 比亚迪工作体验 #
73692次浏览 279人参与
# 大厂VS公务员你怎么选 #
73872次浏览 677人参与
# 工作中听到最受打击的一句话 #
4912次浏览 86人参与
# 大家实习每天都在干啥 #
106252次浏览 573人参与
# 如何排解工作中的焦虑 #
247505次浏览 2279人参与
# 长城汽车工作体验 #
12898次浏览 16人参与
# 机械人避雷的岗位/公司 #
38598次浏览 261人参与
# 秋招结束之后的日子 #
114135次浏览 1052人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务