Single Number I

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

排序法

复杂度

时间 O(NlogN) 空间 O(1)

思路

先将数组排序，再遍历一遍，找前后都不一样的那个数即可。

哈希表法

复杂度

时间 O(N) 空间 O(N)

思路

遍历一遍数组，用哈希表将每个数字出现的次数记下。然后再遍历一遍数组找出出现次数为1的那个。也可以在第一遍遍历的时候一旦出现三次就在表中删去该数。

位操作法

复杂度

时间 O(N) 空间 O(N)

思路

我们可以利用异或的特性。一个数异或0，得到这个数本身，一个数异或本身，得到0。所以我们把所有数异或一遍，出现两次的数就变成0，一次的数就是本身，留下来了。

代码

public class Solution {    public int singleNumber(int[] nums) {        int res = 0;        for(int i = 0 ; i < nums.length; i++){res ^= nums[i];        }        return res;    }}

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

位计数法

复杂度

时间 O(N) 空间 O(1)

思路

如果把所有数的每一位单独累加起来的话，如果这一位累加和是3的倍数，说明出现一次的那个书在这一位肯定是0，不然肯定有3*n+1个1。同理，如果不是3的倍数，则是1。

代码

public class Solution {    public int singleNumber(int[] nums) {        int[] bits = new int[32];        int res = 0;        for(int i = 0; i < 32; i++){for(int j = 0; j < nums.length; j++){    // 累加所有数中该位1的个数    bits[i] += (nums[j] >> i) & 1;}res |= (bits[i] % 3) << i;        }        return res;    }}

位异或法

复杂度

时间 O(N) 空间 O(1)

思路

我们用三个变量分别记录出现一次的数，出现两次的数和出现三次的数。出现一次ones的数计算方法和I是一样的，异或就行了。出现两次twos的条件是ones中有该数，而该数又出现了。出现三次threes的条件是即出现在ones里又出现twos里。如果一个数出现了3次，我们就要把ones和twos中清除该数。

代码

public class Solution {    public int singleNumber(int[] nums) {        int ones = 0, twos = 0, threes = 0;        for(int i = 0; i < nums.length; i++){// 出现两次twos的条件是ones中有该数，而该数又出现了twos |= ones & nums[i];// 出现一次ones的数计算方法和I是一样的，异或就行了ones ^= nums[i];// 出现三次threes的条件是即出现在ones里又出现twos里threes = ones & twos;// 将出现三次的数从ones和twos中去除twos &= ~threes;ones &= ~threes;        }        return ones;    }}