题目:
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?
思路:
这道题目思路对了就不难,否则解起来就比较痛苦了。它考查的其实是位操作。位操作中的异或有一个特点,就是两个相同的数异或之后变成0,而0和某个数异或的结果会是这个数本身。利用这个性质,我们只要遍历数组中的所有数,将它们都进行异或运算,就得到了最终要求的结果。算法的时间复杂度是O(n),空间复杂度是O(1)。
代码:
class Solution {
public:
int singleNumber(vector<int>& nums) {
if (nums.size() == 0) {
return 0;
}
int value = nums[0];
for (int i = 1; i < nums.size(); ++i) {
value = value ^ nums[i];
}
return value;
}
};