Hi all,

I have a different solution here which take no extra memory. This algorithm is based on the three way partition method. First, choose a element in the array as pivot. Second, split this array to three partition, less than pivot, equal to pivot and greater than pivot. Now we have three partitions and we also know the size of these three partitions too. If the single number in any partition, the size of this partition must be 2*n+1, and should not be divisible by 2. Last, we just recursively find the single number in the partition which size can not be divisible by 2.

This method can be easily modified to solve the single number 2 problem.

```
void swap(int A[], int a, int b)
{
int t = A[a];
A[a] = A[b];
A[b] = t;
}
void threeWayPartition(int A[], int n, int&l, int&h)
{
int pivot = A[0];
int j = -1;
int k = n;
for (int i=0; i<k;)
{
if (A[i] < pivot)
{
swap(A, i, ++j);
i++;
}
else if (A[i] > pivot)
{
swap(A, i, --k);
}
else
{
i++;
}
}
l = j;
h = k;
}
#define APPEAR_NUMBER (2)
class Solution {
public:
int singleNumber(int A[], int n) {
if (n==1)
{
return A[0];
}
int l=0;
int h=0;
threeWayPartition(A, n, l, h);
int p = l+1;
if (A[p] != A[p+1])
{
return A[p];
}
else if(p%APPEAR_NUMBER == 0)
{
return singleNumber(A+(p+APPEAR_NUMBER), n-(p+APPEAR_NUMBER));
}
else
{
return singleNumber(A, p);
}
}
};
```