美团笔试题
有一道笔试题是有一个数组中,只有一个数字出现了一次,其他数都出现了三次,让找出这个只出现一次的数。
题目其实比较简单,由于没有OJ,也只是要求了线性复杂度,我就单纯的用HashMap来计数,然后返回count=1的那个数;这样空间复杂度是O(n),如果输入很大就会MLE。不过这个方法在Leetcode上面是AC了的。。。。
后来想到可以用位数组来表示,即如果不包括那个特别数,每一位出现的次数应该是3,所以每一位的出现次数mod
3得到数就是那个特别数,这样的空间复杂度就是O(1)。
想讨论一下我的方法是否算错。。。
#美团#