數(shù)組中數(shù)字出現(xiàn)的次數(shù) II
題目描述
在一個數(shù)組 nums 中除一個數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了三次藕届。請找出那個只出現(xiàn)一次的數(shù)字。
示例：
輸入：nums = [3,4,3,3]
輸出：4
輸入：nums = [9,1,7,9,7,9,7]
輸出：1
提示：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
題目分析
這題目一開始是用哈希表來做的中剩，步驟如下：
- 如果數(shù)字不在哈希表里诫咱，put進去，value為1
- 如果數(shù)字在哈希表里刃唤，且value為1隔心，將其更新為2
- 如果數(shù)字在哈希表里，且value為2尚胞，則將數(shù)字移除哈希表
- 遍歷完成后硬霍，哈希表KeySet里唯一的數(shù)字就是出現(xiàn)一次的數(shù)字
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int num : nums) {
if (hashMap.containsKey(num))
if (hashMap.get(num) == 1)
hashMap.put(num, 2);
else
hashMap.remove(num);
else
hashMap.put(num, 1);
}
return (int) hashMap.keySet().toArray()[0];
}
提交上去之后發(fā)現(xiàn)擊敗了10%的用戶，頓時呆了眼笼裳，怎么說也是O(N)的算法吧唯卖，怎么會這么差（可能是我吃Java不透，造成了過多的性能消耗）躬柬！
然后就想著之前做的這一題的easy版本拜轨，其他數(shù)字出現(xiàn)過兩遍，然后根據(jù)兩個相同數(shù)字的異或為0這個天才結(jié)論允青，將所有數(shù)字異或的結(jié)果返回回去橄碾，按道理說升級版的題目應(yīng)該也能用位運算來做，就開始寫寫畫畫...
一個int型數(shù)有32位颠锉，分別有多少數(shù)字在第i位為1法牲，例如【3 3 1 3】序列里，第一位為1的數(shù)字有4個琼掠，第二位為1的數(shù)字有3個拒垃，顯然，因為第一位%3 != 0瓷蛙，那個唯一的數(shù)的第一位就是1恶复，因為沒人和它湊成三個1；而第二位%3 == 0速挑，說明那一個唯一的數(shù)的第二位不為1谤牡；這樣就很容易得到唯一的數(shù)32個位的具體情況！
public int singleNumber2(int[] nums) {
int now = 1;
int ans = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (int num : nums) {
if ((num & now) != 0)
cnt++;
}
if (cnt % 3 == 1)
ans |= now;
now <<= 1;
}
return ans;
}
強大的位運算時間復(fù)雜度也是O(N)姥宝，但是提交上去之后還是傻了眼翅萤，只擊敗58%的人，然后只能乖乖的看題解了；
題解里面有大牛用自動機的理論寫了一個短小精悍的代碼套么！感興趣的可以去搜一下培己。
最讓我不解的是，題解出現(xiàn)了排序方法胚泌，我對它進行了一些優(yōu)化之后竟然擊敗了80%的用戶（Java的內(nèi)置排序已經(jīng)優(yōu)化到O(N)了省咨？）
public int singleNumber3(int[] nums) {
if (nums.length == 1)
return nums[0];
Arrays.sort(nums);
int index = 0;
while (index < nums.length - 1) {
if (nums[index] != nums[index + 1])
return nums[index];
index += 3;
}
return nums[nums.length - 1];
}
