题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
题解
一个丑陋的版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int singleNumber(vector<int>& nums) {
int vsize = nums.size();
map<int, bool>m;
for (int i = 0; i < vsize; i++)
{
if (m.count(nums[i]))
{
m.erase(nums[i]);
}
else
m[nums[i]] = false;
}
return (*m.begin()).first;
}
|
改进
数学公式：2∗(a+b+c)−(a+a+b+b+c)=c
1
2
3
4
| int singleNumber(vector<int>& nums) {
set<int>st(nums.begin(), nums.end());
return 2 * accumulate(st.begin(),st.end(),0) - accumulate(nums.begin(), nums.end(), 0);
}
|
异或位操作才是最强的：对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位；对相同的二进制位做 XOR 运算，返回的结果是 0。XOR 满足交换律和结合律。将所有的数进行 XOR 操作，得到那个唯一的数字。
1
2
3
4
5
6
| int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i<nums.size(); i++)
res ^= nums[i];
return res;
}
|
挺自闭的，找个简单题 写了早早睡吧。