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

所以只要将所有元素逐个异或就好了，注意要求线性时间因此不能通过排序来做，因为线性时间的排序都对数据有要求，比如要求数据有明确的上限或者分布随机等。

single number