136 single number這題是從一串都出現(xiàn)過2次的數(shù)字里找出只出現(xiàn)了1次的那個數(shù)字，137 single number II 是從一串都出現(xiàn)過3次的數(shù)字里找出只出現(xiàn)了1次的那個數(shù)字相叁。
136
有4種做法。
brute force
對每個數(shù)字都向左右搜索踪危，看有沒有重復(fù)的步脓，沒有就輸出∠踉恚或者顷窒，用一個list蛙吏，遇到第一個的時候add，遇到第二個時候remove鞋吉。時間都是O(n2)鸦做。HashMap
記錄每個數(shù)字出現(xiàn)的次數(shù)。不夠最后還要遍歷一遍谓着。時間是O(n)泼诱。Math
用set保存數(shù)字，2?(a+b+c)?(a+a+b+b+c)=c赊锚，最后singleSum *2 - sum就是結(jié)果治筒。問題是如果數(shù)字是INTEGER的最大值，加起來或者乘法都會溢出舷蒲。位運(yùn)算
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
137
上述1,2,3都適用耸袜，3仍有溢出問題，4不適用了牲平。
我有種方法堤框，先排序，然后用一個count=3 來遍歷纵柿，如果后一項(xiàng)等于前一項(xiàng)蜈抓，那count--，否則判斷count 如果不等于1昂儒，return 前一位沟使，等于一就把count置3然后跳過本次循環(huán)。時間是O(nlogn)渊跋。
這題太難了腊嗡，bit manipulation真是太難了：
這個O(32n)的方法稍微好理解點(diǎn)：
https://discuss.leetcode.com/topic/43166/java-o-n-easy-to-understand-solution-easily-extended-to-any-times-of-occurance
考慮：
...000111000...
...001001000...
...000111000...
...000111000...
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < 32; i++) {
int sum = 0;
for(int j = 0; j < nums.length; j++) {
if(((nums[j] >> i) & 1) == 1) {
sum++; //把每一個數(shù)字同一位的1加起來撤缴，0不用動
sum %= 3; //到3就set到0
}
}
if(sum != 0) {
ans |= sum << i;//把sum（其實(shí)就是1，如果出現(xiàn)兩次的話叽唱，也可以為2）復(fù)原到原來的位置
}
}
return ans;
}
參考：http://www.reibang.com/p/951100bb18c7
我覺得位運(yùn)算的題目不太容易考，很晦澀微宝，看得很絕望棺亭。
