给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 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 - 位运算处理数组中的数 - 代金桥 - 博客园
咯咯咯
网友评论