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?
这个题目的难点在于如何在线性时间内搜索到这个single number，否则我们可以很快给出一个简单的思路：
比如建立两个新的数组，每次把数据插入到新的数组时检查一遍是否已经存在，如果存在就在另一个数组中存2，否则存1，那么我们最后就可以找到数值为1的single number又或者我们可以对数组进行排序，然后再搜索一遍，也能找到single number，但是这两种方法都不能达到要求，第一种显然是O(那么我们就换种思路，我们知道异或是相同为0，不同为1的，如果我们把整数当做二进制数来考虑的话那么显然只用把所有的数异或就可以知道哪个数字是single number了，原因在于异或操作是可交换的，相当于把所有相同的数放在一起，不同的数放在最后，那么显然最后剩下的数就是single number了。
基于这个思路，程序如下：
#include<iostream>#include<vector>using namespace std;int main(){ vector<int> num; int a,n; cin>>n;//输入要比较的数字个数 for(int i=0;i<n;i++) { cin>>a;//输入要比较的数字 num.push_back(a); } int res=0; for(int j=0;j<n;j++) { res ^= num[j]; } cout<<res; return 0;}很明显算法的复杂度是线性的，即O(n)。
新闻热点
疑难解答
