[LeetCode] Single Number I, II

Single Number I

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

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

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?

思路：Single Number I

和find duplicate正好相反，但是仍然可以用排序或hash table解决。排序以后，对每个坐标i，查找A[i-1], A[i+1]中是否有等于A[i]的，没有则为要找的数。或者用hash table/set来记录扫描过的数字。如果A[i]不在hash table中，则插入，如果已经在，则在hash table中删除，最后table中剩下的就是要找的数。但排序法事件复杂度是O(nlogn)，而hash table尽管是O(n)事件复杂度，需要o(n)的extra memory。

这题的终极解法是利用位运算中的异或：x^x = 0, x^0 = x。并且异或有交换律：1^1^0 = 0 = 1^0^1。所以如果将全部数字进行异或运算，所有重复元素都会被消除，最后的结果便是那个唯一的数。

1 2 3 4 5 6 7 8 9

class Solution { public: int singleNumber(int A[], int n) { int res = 0; for(int i=0; i<n; i++) res ^= A[i]; return res; } };

思路：Single Number II

由于x^x^x = x，无法直接利用I的方法来解。但可以应用类似的思路，即利用位运算来消除重复3次的数。以一个数组[14 14 14 9]为例，将每个数字以二进制表达：

1110

1110

1110

1001

_____

4331    对每一位进行求和

1001    对每一位的和做%3运算，来消去所有重复3次的数

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: int singleNumber(int A[], int n) { int res = 0; for(int i=31; i>=0; i--) { int sum = 0; int mask = 1<<i; for(int j=0; j<n; j++) { if(A[j] & mask) sum++; } res = (res<<1) + (sum%3); } return res; } };