求數組中出現一次的數字

求數組中出現一次的數字

代碼如下：

int onediffent(int a[],int n)
{
	int temp=0;
	for(int i=0;i
 

補充：任何數與零異或等於任何數.任何數與自己相異或為0；

假如問題變成一個數組中有兩個數字出現一次，其余別的數字都出現兩次，那麼如何求出這兩個數字呢？

算法思路：首先將數組中的一組數字異或，結果存在temp中，然後計算出temp中最低位出現的位置，然後再和數組中所有的數字相與，這樣就將數組分成了兩個數組，問題轉換為一個數組中只有一個數字出現一次的情況。

代碼如下：
int twodiffent(int a[],int n)
{
	int temp,count,i,j,k;
	temp=a[0];
	j=k=0;
	int b[n],c[n];

	for(int i=1;i>1;
		count*=2;
	}
	//將兩個數字分別分到兩個數組中，問題轉換為一個數組中只有一個出現一次的數.
	for(i=0;i在算法群裡某熱心網友不吝賜教得到目前最優解，相對比算法二優化了至少一個世紀<囧>,代碼如下：
 
void solve(int num[],int n)
{
        int x = 0;
        for(int i = 0; i < n; ++i)
        {
            x = x ^ num[i];
        }
        int smallestOne = x & -x;
        int a = 0;
        int b = 0;
        for(int i = 0; i < n; ++i)
        {
            if((num[i] & smallestOne) != 0)
                a = a ^ num[i];
            else
                b = b ^ num[i];
        }
       printf("%d %d\n",a,b);
}


 
該算法中x&-x是算出最低位的1，負數在計算機中是以補碼表示，例如4&-4=4，1000&-1000=8 表示數字4中二進制位1最低位是在權為2^2出現，數字1000二進制位1最低位是在權值為2^3出現.算法二中的數組完全沒有必要使用，空間復雜度為O(1),時間復雜度O(n);
如果你有更好的方法，不妨在此討論.