深信服笔试，给出n个数和n-1个数找出少了哪个数，怎么用哈希
昨天做的一道深信服的编程题。给出n个数和n-1个数，要求找出少了哪个数。顺序会被打乱，要求时间复杂度为O（n）。
当时是准备用空间换时间，用一个超大的bool数组，使n-1个数对应的数组位置为真，再对n个数遍历对应boo数组的位置，为假的就是少的。后来同学一跟我说用hash才恍然大悟，但是我没有用过C++里面的hashmap，这个要怎么用啊，请教一下。（出来才查到求和再相减）。。
#深信服#
2019-03-10 16:15 湖北工业大学 数据分析师
关注
全部评论
牛客8110830
富途_web开发
异或更简单
W矩阵
阿里云_开发工程师
面试官让我用数学方法重写做一下，我说重新加起来再减下去不会溢出吗...
宝可龙宝
杭州电子科技大学 后端
异或是正确答案。。
愿用单身50年换头像里的高楼
哈尔滨工业大学 C++
hashmap不太可能o(n)吧
25Y
湖南科技大学 Java
异或 n^m^n=m m就是少的那个数
七夜zmn
景德镇陶瓷大学 Java
将多的数加入map。存储出现的次数。少点那个数组去get。然后移除。剩的就是多的
相关推荐
字节跳动公司氛围 558人发布
