美团笔试题

有一道笔试题是有一个数组中,只有一个数字出现了一次,其他数都出现了三次,让找出这个只出现一次的数。

题目其实比较简单,由于没有OJ,也只是要求了线性复杂度,我就单纯的用HashMap来计数,然后返回count=1的那个数;这样空间复杂度是O(n),如果输入很大就会MLE。不过这个方法在Leetcode上面是AC了的。。。。

后来想到可以用位数组来表示,即如果不包括那个特别数,每一位出现的次数应该是3,所以每一位的出现次数mod 3得到数就是那个特别数,这样的空间复杂度就是O(1)。

想讨论一下我的方法是否算错。。。
#美团#
全部评论
请问怎么确定位数组的大小,题目说的是给一个整数数组
点赞 回复 分享
发布于 2016-10-11 22:54
没错,很正确
点赞 回复 分享
发布于 2016-10-11 22:54
没错,当时leetcode也有人给出了这种方法
点赞 回复 分享
发布于 2016-10-11 23:58
你所说的位数组怎么实现呢?我理解另外需要一个长为32的数组来统计每一位上1出现的次数,是这样吗?
点赞 回复 分享
发布于 2016-10-12 00:38

相关推荐

牛客717484937号:双飞硕没实习挺要命的
点赞 评论 收藏
分享
10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务