?前言?：
演算法是一個程式員的內功，能很好的體現程式員的編程思維，通過學習和掌握常見的演算法，不僅能提高coding能力，還能更加容易在筆面試中脫穎而出，本專欄將記錄博主刷演算法題的程序，不定期的會更新一些優質的演算法題，如果對大家有幫助，別忘了三連支持喲！
目錄
?前言?：
?題目描述?
?題目分析?:
按位異或運算子
💎一個單身狗💎
💎兩個單身狗💎
eor&（~eor+1）公式拿到二進制序列最右端的一個1
?具體代碼詳解?:
?題目描述?
💡：
描述：
輸入一個陣列，陣列中只有兩個元素出現了一次，其它元素均出現了兩次，
示例：
輸入：1,4,5,8,9,2,1,5,9,4
輸出：8 2
?題目分析?:
在解決這道題目之前我們首先來了解一下按位異或運算子的一些操作
按位異或運算子
1：首先按位異或是位運算子，操作的是二進制的位元位
2：其具體運算程序可以記為：相同為0，相異為1，當然也可以理解為無進位加法
3：a^a=0 a^0=a
任何一個數按異或上自己為0，按位異或上0等于它本身
4：按位異或運算支持交換律和結合律
🔑：現在我們了解了按位異或運算子，在解決這個問題前，我們先解決它的簡化版本：一個陣列中只有一個元素出現了一次，其它元素均出現了兩次
💎一個單身狗💎
🔑這題的難點就在于我們是否能正確的理解按位異或運算的運算子，其實按位運算有一個功能：
如果我們把陣列中的所有元素按位異或起來，利用交換律和結合律把所有相同的聚在一起，這時如果出現偶數次的元素就會消除掉，出現偶數次的就會保留下來，因此我們遍歷一遍陣列，將所有元素按位異或起來，得到的結果就是那個只出現一次的數字，
int num = 0;//把只出現一次的數字放在num中去
void FindAppearSingalNum(int arr[], int sz)
{
int i = 0;
for (i = 0; i < sz; i++)
{
num ^= arr[i];
}
}💎兩個單身狗💎
🔑：在解決完一個單身狗后我們知道，我們可以遍歷一遍陣列，將陣列中的所有元素按位異或起來，這樣就可以消除出現偶數次的元素，但是有一個問題：
因為陣列中有兩個元素出現一次，所以遍歷一遍后eor=num1^num2;其中num1和num2是那個只出現一次的數字，
1：由于陣列中有兩個單身狗，所以num1!=num2,這就保證了eor！=0，所以在eor的二進制序列中一定會有一個1.
2：因為eor是由num1^num2的結果，所以在eor二進制中從右往左數第一個1處，num1和num2
在這一位元位上一定存在不同，那么我們利用分治法，將陣列中這一位元位上是1的元素分成一組，將陣列中這一位元位是0的元素分成一組，我們可以保證在每一組中都有唯一一個單身狗，這樣把每一組按位異或起來，就能得到這兩個單身狗，
💡：現在這個問題就轉化為了如何拿到eor中從右往左的第一個1
eor&（~eor+1）公式拿到二進制序列最右端的一個1
圖解：
?具體代碼詳解?:
#include<stdio.h>
int num1 = 0;
int num2 = 0;
void FindAppearSingalNum(int arr[], int sz)
{
//1:遍歷一遍將所有數都按位異或起來
int i = 0;
int eor = 0;
for (i = 0; i < sz; i++)
{
eor ^= arr[i];
}
//eor=num1^num2
//2:取出eor最右端的1作為區分值
int rightOne = eor & (~eor + 1);
for (i = 0; i < sz; i++)
{
if (rightOne & arr[i])
{
num1 ^= arr[i];
}
else
{
num2 ^= arr[i];
}
}
}
int main()
{
//測驗用例
int arr[] = { 1,4,5,8,9,2,1,5,9,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
FindAppearSingalNum(arr,sz);
printf("這兩個單身狗是:%d %d\n", num1, num2);
return 0;
}以上代碼，還可做優化在此僅作參考，若有更好的演算法，還望能夠私信告知，多謝各位，
由于本人水平十分有限，若有錯誤請即使告知！如果有幫助別忘了，萬分感謝，
點贊👍 收藏? 關注?
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303581.html
標籤：java