1. 题目
1.1 英文题目
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
1.2 中文题目
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
1.3输入输出
| 输入 | 输出 |
|---|---|
| nums = [2,2,1] | 4 |
| nums = [4,1,2,1,2] | 4 |
| nums = [1] | 1 |
1.4 约束条件
- 1 <= nums.length <= 3 * 104
- -3 * 104 <= nums[i] <= 3 * 104
- Each element in the array appears twice except for one element which appears only once.
2. 分析
这一题我的第一反应是暴力搜索，先构建一个临时数组存储已遍历元素。若新遍历元素与之前重复，则不是目标值，从临时数组中删除；否则加入。遍历到最后，临时数组内只剩余目标值。代码如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> temp;
vector<int>::iterator iter;
for (int i = 0; i < nums.size(); i++)
{
iter = find(temp.begin(), temp.end(), nums[i]);
if (iter != temp.end()) //找到了，重复元素
temp.erase(iter);
else
temp.push_back(nums[i]);
}
return temp[0];
}
};
之后又看了下一些其他大神们的写法，让人直呼妙哉！其中一种是利用set集合不含重复元素的性质，通过将数组转为集合，之后用集合元素和的2倍减去原数组所有元素的和，就是结果，代码如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
set<int> setNums(nums.begin(), nums.end());
int sum = accumulate(nums.begin(), nums.end(), 0);
int setSum = accumulate(setNums.begin(), setNums.end(), 0);
return 2 * setSum - sum;
}
};
上面这种算法在时间和空间消耗上并不是太好，但是这种想法不错。另外还有一种做法是利用异或的性质，假设所有的数组为：abcbcda,则
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d。
代码如下：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int result = 0;
for (auto num : nums)
result ^= num;
return result;
}
};
3. 补充知识
（1）vector
a. 查找vector中的某一个元素
可以利用algorithm头文件中find()，用法为：
vector<A>::iterator iter = std::find(vec.begin(), vec.end(), findNum);
b.vector删减元素
- push_back()尾部添加元素
- pop_back()尾部删除元素
- erase(num)删除指定元素或指定迭代器位置元素
c.vector与set互转
- vector转set:
set<int> st(v.begin(), v.end());//在构造函数中可以直接实现vector转set - set转vector:
v.assign(st.begin(), st.end());
(2) 异或
a.异或的特性：
- 恒定律：A ^ 0 = A
- 归零率：A ^ A = 0
- 交换律：A ^ B = B ^ A
- 结合律：(A ^ B) ^ C = A ^ (B ^ C)
b.用途
异或可以快速比较两个值是否相等 a ^ b == 0，效率非常高，比 a - b == 0 高很多。
异或还能在不定义临时变量的情况下，交换两个值（经典题目）
a = a ^ b
b = a ^ b // a ^ b ^ b = a ^ 0 = a
a = a ^ b // a ^ b ^ a = b ^ 0 = b
参考：https://www.jianshu.com/p/e3442ed3d874