本文共 1702 字，大约阅读时间需要 5 分钟。

链接：

大意：

给定一个数组nums，数组中除了一个数字只出现了1次，其余数字都出现了3次。要求找出这个数字，最好时间复杂度为O(n)，空间复杂度为O(1)。例子：

思路：

顺势而来的是一种使用32长度的整型数组思路。

1. 构造一个整型数组bytes。 bytes[i]意为nums中每个数的二进制表示在第i位的和
2. 由于除了一个数字只出现了1次，其余数字都出现了3次。则对于bytes[i]要么是3的倍数，要么是3的倍数加1
3. 如果bytes[i]是3的倍数，则只出现了1次的那个数在该位为0；否则在该位为1
4. 最后构造出这个数字

代码：

// 使用额外储存空间class Solution {    private final int MOD = 3; // MOD：数组中除了一个数只出现一次，其余数字都出现了MOD次    public int singleNumber(int[] nums) {        int[] bytes = new int[32];        for (int num : nums) {            int i = 0;            while (i < 32) {                if (((num >> i) & 1) == 1)                    bytes[i]++;                i++;            }        }        int res = 0;        for (int i = 31; i >= 0; i--) {            if (bytes[i] % MOD == 1) {                res += (1 << i);            }        }        return res;    }}

 结果：

结论：

效率确实低，有待改进。

改进：

发现可以不使用数组，而用一个计数变量count1记录在每一位置为1的二进制数的个数。若count1%3==1 则目标数在该位置也为1。此外，该解法时间复杂度为O(32*n)...(也算线性时间吧）空间复杂度为O(1).

// 不使用额外储存空间class Solution {    private final int MOD = 3; // MOD：数组中除了一个数只出现一次，其余数字都出现了MOD次    public int singleNumber(int[] nums) {        int res = 0;        for (int i = 0; i < 32; i++) {            int count1 = 0; // 记录某位置为1的二进制数的个数            for (int num : nums) {                if (((num >> i) & 1) == 1)                    count1++;            }                if (count1 % MOD == 1)                res += (1 << i);        }        return res;    }}

效率仍旧低，有待改进。。。 

最佳：

参考：  

// 不使用额外储存空间// ^ | & 都是满足交换和结合律的class Solution {    public int singleNumber(int[] nums) {        int a = 0, b = 0; // 当num第一次出现时，储存在b中 第二次出现时，存储在a中  第三次出现时 a和b都清空        for (int num : nums) {            b = b ^ num & ~a;            a = a ^ num & ~b;        }        return b;    }}

转载地址：http://ixesi.baihongyu.com/