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

相关推荐

点赞 6 评论
分享
牛客网
牛客企业服务