一、題目介紹：
一個整形數組裡，存在兩個只出現過一次的數字，其他數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間複雜度時O（n），空間複雜度時O（1）。
例如輸入數組{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4,3 }，只有1和2出現了一次，其他數字都出現了兩次，所以輸出1、2。
二、分析：
1、看到這個題，我們的第一想法就是排序，只要將數據有序，只要數據和它右邊的數據不相等，則只出現一次的數據就找到了。
這種方法主要就是排序算法，但是排序算法的時間複雜度達不到題目要求的O（n），所以這個方法是行不通的，只能另想他法。
2、題目要求找兩個只出現了一次的數據，那麼我們可以簡化一下，先假設找出有一個只出現了一次的數據。
這時我們可以將思維發散一下，用二進制位運算思考，那麼此時我們就用^(異或)，此運算符是兩個位不同則為1，那麼兩個數相同，則他的二進制位都是相同的，
相同的數異或後的值為0，那麼從數據開始逐個異或到尾，結果就是出現一次的那個數。
3、但是題目要求為有兩個只出現了一次的數據，如果還用剛才的方法，最終的結果則是兩個數據異或後的值，但是不同的兩個數異或後的結果也可能相同，
那麼此時我們就將兩個不同的數分開到不同的兩組，再用異或的辦法找到只出現一次的數。
這不同的兩個數的二進制，至少會有一個位是不同的，那麼只要我們將這個不同的位找到，在與這兩個數異或，就可以把他們分到不同的兩組，相同的兩個數和這個位異或後的值肯定都是相同的，那麼就可以把整個數組分成兩部分，然後找到這兩個數。
三、代碼展示：
//查找函數（有一個只出現了一次的數）
int Find1(int* arr,int len)
{
int tmp = 0;
for (int i = 0; i < len; i++)
{
tmp ^= arr[i];
}
return tmp;
}
//劃分函數，將兩個單獨的數據分開
int Partition(int *arr,int L,int R,int n)
{
while ( L != R)//用快排的思想將數組分成兩部分。
{
while (L != R)
{
if ((arr[L] & n) == 0)
{
L++;
}
else
{
break;
}
}
while (L != R)
{
if ((arr[R] & n) == 1)
{
R--;
}
else
{
break;
}
}
swap(arr[L],arr[R]);
}
return L;
}
//查找函數（有兩個只出現了一次的數）
void Find2(int *arr, int len)
{
int tmp = Find1(arr, len);//tmp保存的是兩個不同的數異或後的值。
int n = 1;
while (tmp != 0)//找到不相同的位
{
if ((n & tmp) == 0)
{
n <<= 1;
}
else
{
break;
}
}
int L = Partition(arr, 0, len - 1, n);//用不同的二進制位將數組劃分成兩部分。
cout << Find1(arr, L) ;
cout <}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4,3 };
int len = sizeof(arr) / sizeof(arr[0]);
Find2(arr,len);
return 0;
}
分享到:
閱讀更多 cpp軟件架構獅 的文章
