只出現(xiàn)一次的數(shù)字
題目鏈接
思路
要求為線性時(shí)間復(fù)雜度，即時(shí)間復(fù)雜度為O(n)，那么我們就不能用簡單的兩層循環(huán)來解決問題
要求只能使用常量額外空間，即空間復(fù)雜度為O(1)，那么我們就不能額外開辟一個(gè)數(shù)組來記錄每個(gè)元素出現(xiàn)的次數(shù)
這里，給大家介紹一個(gè)全新的方法：位運(yùn)算——異或^
注：如果對位運(yùn)算符還不太了解，建議先看看??位運(yùn)算詳解
異或的特性：
異或是支持交換律的：
a ^ b ^ c=b ^ a ^ c
a ^ a = 0（相同的數(shù)異或?yàn)?）
0 ^ a = a（一個(gè)數(shù)和0異或得到的還是本身）
那么我們就可以利用異或的這些特性，來解決這個(gè)問題。
題目告訴我們，數(shù)組中除某一個(gè)元素只出現(xiàn)一次外，其余元素都出現(xiàn)了兩次，那么我們將數(shù)組的所有元素都異或到一起，不就可以得到只出現(xiàn)一次的那一個(gè)數(shù)了嗎？文章來源：http://www.zghlxwxcb.cn/news/detail-617470.html
實(shí)現(xiàn)代碼
int singleNumber(int* nums, int numsSize)
{
int ret = 0;
for(int i = 0; i < numsSize; i++)
ret ^= nums[i];
return ret;
}
通過這一道題，最重要的就是掌握異或的特性，這有利于后續(xù)許多問題的解決文章來源地址http://www.zghlxwxcb.cn/news/detail-617470.html
到了這里，關(guān)于每日一題——只出現(xiàn)一次的數(shù)字的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
