1 class Solution { 2 public: 3 int singleNumber(int A[], int n) { 4 int result=A[0]; 5 for(int i=1;i<n;i++) 6 result^=A[i]; 7 return result; 8 } 9 };
这个如果看过CSAPP并做过它的lab 1的话就可以对位运算有很好的认识，异或有很好的性质：
1. a^a=0,0^a=a
题目中说只有1个元素是单个的，其它都是成对的，所以
a1^a2^b1^b2……^x=0^0^0……^x=x
所以只要将所有元素逐个异或就好了，注意要求线性时间因此不能通过排序来做，因为线性时间的排序都对数据有要求，比如要求数据有明确的上限或者分布随机等。
原文：http://www.cnblogs.com/gaoduan/p/4055315.html