【演算法】異或演算法找缺失的數
leetcode面試題17.04–消失的數字及其變式
先贊后看好習慣 打字不容易，這都是很用心做的，希望得到支持你 大家的點贊和支持對于我來說是一種非常重要的動力 看完之后別忘記關注我哦！???
文章目錄
- 異或演算法
- 【例題】leetcode面試題17.04--消失的數字
- 演算法及其原理
- 代碼實作
- 【變式】leetcode-劍指offer56-I-陣列中數字出現的次數
- 題目分析
- 演算法及其原理
- 代碼實作
- 尾聲
異或演算法
【例題】leetcode面試題17.04–消失的數字
演算法及其原理
異或演算法
原理：兩個相同的數字互相異或結果是0，任何數異或0是它本身，
所以上面這道題的思路：
1.宣告一個整型ret變數記錄結果，把nums陣列里面所有的數異或在一起，賦給ret，
2.讓0-n里面所有的數異或在一起，然后再與ret異或，最后就是得到我們缺失的數字，
因為每個數字再經歷兩次回圈異或之后，出現的數字相當于自己異或了自己，剩下0-N中，nums里面沒有出現的數字異或一個0，也就是最后ret就是我們缺失的數字，
代碼實作
int missingNumber(int* nums, int numsSize){
int ret=0;
for(int i=0;i<numsSize;i++)
{
ret^=nums[i];
}
for(int i=0;i<=numsSize;i++)
{
ret^=i;
}
return ret;
}
以上這道題在leetcode的題庫里面，算是比較簡單的一道題，當然對于初學的伙伴來說，我們如果拋開時間復雜度一定要是O(N)這個條件的話，我們還可以采取一種思路更簡單的方式：排序后再找出來，
排序后，我們直接找哪兩個數字之間不是相差1即可，
【變式】leetcode-劍指offer56-I-陣列中數字出現的次數
相對于上一題，本題的思路較為復雜
題目分析
此題對于上一題，其實如果只是找一個只出現一次的數字，對于我們來說是非常簡單的，我們只需要將所有數字異或在一起就可以了，
但是，此題的難點就在于，我們要找的是兩個只出現一次的數字，
如果還是按照上面的方式全部異或在一起，我們得到的結果就是那兩個單獨出現的數字相互異或的結果，
例子：假如nums[]={1，1，2，2，3，3，5，6}；
假設我們還是按照上面那樣，全部異或在一起，我們得到的結果是5^6,而不是5和6，所以死套上面的方法是不可行的，
但是，如果我們將那兩個單獨出現的數字分開，分到兩個組里面，每個組里面的數字相互異或，我們不就可以得到那兩個數字了嗎？
所以，我們把問題轉化為了：如何將兩個只出現一次的數字分開？
我們要知道，兩個不同數字做按位與運算（&）的時候得到的結果的二進制位的每一位代表了兩個數字每一位是否相同，
可能很多小伙伴并不理解這句話，下面我來解釋一下，我們就以上面那個陣列里面的5，6來舉例，
（32位高位的0省略不寫）
5的二進制位：0101
6的二進制位：0110
5和6的異或結果：0011
異或的結果0011可以告訴我們很多資訊：
因為異或^運算：位相同得0，相異得1，因此，0011告訴我們，5和6的第一位，第二位不同，第三位，第四位相同，
因次我們可以用5，6的第一位（或者第二位）來分開它們，
也就是說，我們可以將陣列分為兩組，一組每個數字第一位為1的，一組是每個數字第一位為0的，
演算法及其原理
有了上面的鋪墊，我們就可以知道我們該題的演算法是怎么實作的了，
1.將所有數異或在一起
2.計算異或的結果ret哪一位是1，得到位置pos
3.將陣列中第pos位為1的放在一組里面，并且異或在一起，將陣列中第pos位位0的放在另一組里面，異或在一起，
這樣我們就可以得到兩個我們想要的，只出現一次的數字了，
代碼實作
int* singleNumbers(int* nums, int numsSize, int* returnSize)
//nums陣列首元素地址
//numsSize陣列大小
//returnSize回傳陣列的大小
{
//將所有數字異或在一起
int i=0;
int ret=0;
for(i=0;i<numsSize;i++)
{
ret^=nums[i];
}
//找出ret哪一位為1
int pos=0;//記錄位數為1的位置
for(i=0;i<32;i++)
{
if((ret>>i)&1==1)
{
pos=i;
break;
}
}
//按照上面的標準將nums陣列進行分組
int num1=0;//記錄第一個數
int num2=0;//記錄第二個數
for(i=0;i<numsSize;i++)
{
if((nums[i]>>pos)&1==1)
{
num1^=nums[i];
}
else
{
num2^=nums[i];
}
}
//題目要求我們的回傳的陣列要在堆上開辟
int*retArr=(int*)malloc(sizeof(int)*2);
retArr[0]=num1;
retArr[1]=num2;
*returnSize=2;
return retArr;
}
尾聲
以上就是今天異或演算法的全部內容，希望看完的小伙伴都可以有識訓，如果對代碼中一些細節的地方還是不明白的話，可以私信我，
在離開之前不要忘記點個贊點個收藏哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356989.html
標籤：其他