题目描述

在一个数组 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次。请找出那个只出现一次的数字。其实解法是相同的，具体的代码就不写啦~