問題描述
一個陣列中只有兩個數字是出現一次，其他所有數字都出現了兩次，
撰寫一個函式找出這兩個只出現一次的數字，
解決思路
①粗暴解決
- 每一個元素與全部元素遍歷比較，未比較成功則為所要找的數字
- 這里應注意在每次比較時，要跳過元素自己與自己比較的情況
- 時間復雜度 O(n^2)
代碼
void Find(const int* arr, size_t num)
{
for (int i = 0; i < num; i++)
{
int flag = 1;
for (int j = 0; j < num; j++)
{
if (j == i)
{
continue;
} // 跳過元素自己與自己比較
if (arr[j] == arr[i])
{
flag = 0;
break;
}
}
if (1 == flag)
{
printf("%d ", arr[i]);
}
}
}
② 通過異或解決問題
- 將所有元素挨個進行異或運算，因為只有兩個數字不相同，其余數字均能找到相同的一個元素，所以最終得到的結果就是兩個只出現一次的數字的異或結果
- 分類，找到兩個數字在哪一位位元位不同，這樣根據這一位可以將陣列分為兩個部分，為1的部分，為0的部分
- 再異或，在分開的兩部分中，每一部分都只有一個只出現一次的數字，這個數字也就是我們要找的數字之一，這樣對每一部分的每一個元素再異或運算，最終得到的結果就是所要找的數字
代碼
void Find(const int* arr, size_t num)
{
int temp = 0;
for (int i = 0; i < num; i++)
{
temp ^= arr[i];
} // 回圈結束得到的結果為所要找的兩個數字異或運算后的結果
int flag = 0;
while (((temp >> flag) & 1) == 0)
{
flag++;
} // 得到所要找的兩個數字在哪一位位元位不同
int ret_1 = 0;
int ret_2 = 0;
for (int i = 0; i < num; i++)
{
if ((arr[i] >> flag) & 1)
{
ret_1 ^= arr[i];
} // 這是在不同的位元位為1的一組
else
{
ret_2 ^= arr[i];
} // 這是在不同的位元位為0的一組
}
printf("%d %d\n", ret_1, ret_2);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/306281.html
標籤：其他
上一篇：TopK演算法(堆的思想)
下一篇：CSS復合選擇器