给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:输入:[2,2,3,2]输出:3
示例 2:输入:[0,1,0,1,0,1,99]输出:99
我的思路:先将其排序,这样就得到了一个顺序的数组,找到其中与相邻元素不等的就是我们需要寻找的数
代码实现:(不知道怎么总复制不全,敲又懒。。。索性截了图。。。)
其他更高效的解法:
1)统计每一位bit上‘1’的个数,如果结果为3的倍数,说明只出现一次的数字在该bit上的值为0,否则为1,如此计算每一位就可得到结果。
具体讲解参见:LeetCode——Single Number II(找出数组中只出现一次的数2) - 苍枫露雨 - 博客园
2)这个问题之前有一个简单的版本,即其余数字都出现两次,当时用“异或”处理得到了结果(将数组内所有元素进行异或,因为一个数与它本身异或等于0,与0异或等于它本身)。这里,题目更改为出现三次,所以我们不妨借鉴其思路,用二进制模拟三进制对其进行处理。
具体讲解参见:leetcode Single Number II - 位运算处理数组中的数 - 代金桥 - 博客园
咯咯咯