136. Single Number
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?
这道题的思路其实也被应用于missing number中，就是采用异或操作，如果只有一个元素只出现过一次，那么对所有元素采用异或操作后得到的就是single number，代码如下:
/*use bit manipulation 20ms,no extra place*/
class Solution {
public:
int singleNumber(vector<int>& nums) {
int i=0,single=0;
for(i=0;i<nums.size();i++)
single^=nums[i];
return single;
}
};
时间复杂度为O(n)，空间复杂度O(1)，符合题目要求
对于这个题而言，另一种解法是使用hash-table，先建立哈希表，然后遍历数组中的元素，如果该元素不在表中，则将其插入表中;否则将其删除，最后返回表中唯一一个元素即可，代码如下:
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> hash;
int i=0,single;
for(i=0;i<nums.size();i++){
if(hash.find(nums[i])==hash.end())
hash[nums[i]]=i;
else
hash.erase(nums[i]);
}
unordered_map<int,int>::iterator it=hash.begin();
return (*it).first;
}
};
时间复杂度为O(n),空间复杂度为O(n)