题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
题解一
先将数组排序，然后再找出现一次的数字是比较简单的。
时间复杂度为，空间复杂度为
。比较简单，代码省略。
题解二
还有一种想法是以空间换时间，使用一个哈希表来记录数组中每个数字出现的次数，最终可以得到两个只出现一次的数字。
时间复杂度为，空间复杂度为
。比较简单，代码省略。
题解三
如果需要继续优化时空复杂度应该怎么做呢？这里可以沿用上一题的思路，使用位运算来解决。将所有数字的二进制表示的每一位都进行相加，如果某一位的和能够被3整除，那么那个只出现一次的数字在这个位上就是0；若不能整除，那么那个只出现一次的数字在这个位上就是1。
下面是参考代码：
import java.math.BigInteger;
class Solution {
public int singleNumber(int[] nums) {
StringBuilder sb = new StringBuilder(getFullBinaryString(0));
for (int num : nums) {
String numString = getFullBinaryString(num);
for (int i = 0; i < 32; i++) {
sb.setCharAt(i, (char) (sb.charAt(i)+numString.charAt(i)-'0'));
}
}
for (int i = 0; i < 32; i++) {
if ((int) (sb.charAt(i)) % 3 == 0)
sb.setCharAt(i, '0');
else sb.setCharAt(i, '1');
}
return Integer.valueOf(sb.toString(), 2);
}
public String getFullBinaryString(int num) {
String s = Integer.toBinaryString(num);
return String.format("%032d", new BigInteger(s));
}
}
可以将这道题扩展一下，若题目更改为：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了n次。请找出那个只出现一次的数字。其实解法是相同的，具体的代码就不写啦~
