Halo，這里是Ppeua。平時(shí)主要更新C語(yǔ)言，C++，數(shù)據(jù)結(jié)構(gòu)算法......感興趣就關(guān)注我吧！你定不會(huì)失望。

?

🌈個(gè)人主頁(yè)：主頁(yè)鏈接

🌈算法專(zhuān)欄：專(zhuān)欄鏈接

?????我會(huì)一直往里填充內(nèi)容噠！

🌈LeetCode專(zhuān)欄：專(zhuān)欄鏈接?

????目前在刷初級(jí)算法的LeetBook 。若每日一題當(dāng)中有力所能及的題目，也會(huì)當(dāng)天做完發(fā)出

🌈代碼倉(cāng)庫(kù)：Gitee鏈接

🌈點(diǎn)擊關(guān)注=收獲更多優(yōu)質(zhì)內(nèi)容🌈

?

目錄

先來(lái)了解一下異或^:

136.?只出現(xiàn)一次的數(shù)字

137.?只出現(xiàn)一次的數(shù)字 II

260.?只出現(xiàn)一次的數(shù)字 III

完結(jié)撒花：

---

這三個(gè)問(wèn)題都為位運(yùn)算中異或^的特性,所以放在一起. 可以看看之前的這篇文章有對(duì)接下倆涉及的概念lowbitx的具體講解:位運(yùn)算專(zhuān)題

先來(lái)了解一下異或^:

相同為0,不同則為1,這是在二進(jìn)制編碼中

101111^10111=000001010^0101=1111

放到一個(gè)整形數(shù)據(jù)來(lái)看,相同的數(shù)字就被消去了

此外,任意一個(gè)數(shù)異或0都為他本身 (這從二進(jìn)制編碼來(lái)理解也很好理解,0的二進(jìn)制編碼全為0,任意一個(gè)數(shù)與其異或不同的就是若干位的1)

x^x=0
x^0=x

?此外 ,異或滿足結(jié)合律與交換律

a ^ b = c  => a ^ c = b  => b ^ c = a (交換律)
a ^ b ^ c = a ^ (b ^ c) = (a ^ b）^ c (結(jié)合律)

異或的特性就這么多,現(xiàn)在開(kāi)始解題吧.

136.?只出現(xiàn)一次的數(shù)字

給你一個(gè)?非空?整數(shù)數(shù)組?nums?，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法來(lái)解決此問(wèn)題，且該算法只使用常量額外空間。

輸入：nums = [2,2,1]
輸出：1

輸入：nums = [4,1,2,1,2]
輸出：4

輸入：nums = [1]
輸出：1

這題很簡(jiǎn)單,利用異或里同項(xiàng)相消,異項(xiàng)保留的特點(diǎn),直接遍歷^每一個(gè)數(shù)字返回遍歷后的結(jié)果就可以了

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for (auto e: nums) ret ^= e;return ret;}
};

137.?只出現(xiàn)一次的數(shù)字 II

給你一個(gè)整數(shù)數(shù)組?nums?，除某個(gè)元素僅出現(xiàn)?一次?外，其余每個(gè)元素都恰出現(xiàn)?三次 。請(qǐng)你找出并返回那個(gè)只出現(xiàn)了一次的元素。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法且不使用額外空間來(lái)解決此問(wèn)題。

輸入：nums = [2,2,3,2]
輸出：3

輸入：nums = [0,1,0,1,0,1,99]
輸出：99

數(shù)組中有且僅有1個(gè)數(shù)字出現(xiàn)1次 其余均出現(xiàn)了3次。

在32位環(huán)境下一個(gè)數(shù)的二進(jìn)制位由32個(gè)0/1構(gòu)成。取數(shù)組中的每一個(gè)數(shù)的某一二進(jìn)制位相加，得到的一定是三的倍數(shù)，或者三的倍數(shù)加一（當(dāng)那唯一出現(xiàn)一次的數(shù)該二進(jìn)制位也是1的時(shí)候）。
知道這個(gè)規(guī)律后，我們定義一個(gè)初始循環(huán)表示ans的第i位數(shù)。之后內(nèi)嵌一個(gè)循環(huán)遍歷數(shù)組中的每一個(gè)數(shù)。

若總數(shù)不為3的倍數(shù)，則說(shuō)明該位上有唯一出現(xiàn)一次的數(shù)的1，將其拼到ans上。

?

class Solution {
public:int singleNumber(vector<int>& nums) {int ans=0;for(int i=0;i<32;i++){int total=0;for(auto num:nums){total+=(num>>i)&1;}if(total%3){ans|=1<<i;}}return ans;}
};

260.?只出現(xiàn)一次的數(shù)字 III

給你一個(gè)整數(shù)數(shù)組?nums，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個(gè)元素。你可以按?任意順序?返回答案。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法且僅使用常量額外空間來(lái)解決此問(wèn)題。

輸入：nums = [1,2,1,3,2,5]
輸出：[3,5]
解釋：[5, 3] 也是有效的答案。

輸入：nums = [-1,0]
輸出：[-1,0]

輸入：nums = [0,1]
輸出：[1,0]

這題是第一題的升級(jí)版,有兩個(gè)元素恰好出現(xiàn)一次,參照第一題的做法,若將這一個(gè)數(shù)組分為兩個(gè)組,將這唯一出現(xiàn)的兩個(gè)元素分別放入這兩個(gè)組中,執(zhí)行第一題的異或操作,最后剩下來(lái)的就是唯一出現(xiàn)的數(shù)字.

那么如何將兩個(gè)數(shù)字分開(kāi)放呢??

觀察二進(jìn)制位出現(xiàn)的規(guī)律,一個(gè)位就兩種可能,要么是1,要么是0,所以我們只要找到這兩個(gè)數(shù)不相同的那一個(gè)位,以此來(lái)區(qū)分就可

?

先將所有數(shù)據(jù)^,因?yàn)槌@兩個(gè)數(shù)字外,其余都是兩兩出現(xiàn),^后的結(jié)果為這兩個(gè)數(shù)字的結(jié)果.

再用lowbit思想 返回其第一個(gè)出現(xiàn)1的數(shù)字(異或完lowbit返回的是這兩個(gè)數(shù)字第一個(gè)不相同的位)

在進(jìn)行一個(gè)循環(huán)將每一個(gè)數(shù)與這個(gè)數(shù),無(wú)非就兩種結(jié)果,將這兩種結(jié)果分組,即可

#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:vector<int> singleNumber(vector<int>& nums) {vector<int>ans1;vector<int>ans2;vector<int>ans3(2);long tag=0;for(auto n:nums)tag^=n;long ans=0;ans=tag&(-tag);//lowbitfor(auto n:nums){if(n&ans){ans3[0]^=n;}else ans3[1]^=n;}return ans3;}
};

完結(jié)撒花：

🌈本篇博客的內(nèi)容【Leetcode 136、137、260問(wèn)題詳解及代碼實(shí)現(xiàn)】已經(jīng)結(jié)束。

🌈若對(duì)你有些許幫助，可以點(diǎn)贊、關(guān)注、評(píng)論支持下博主，你的支持將是我前進(jìn)路上最大的動(dòng)力。

🌈若以上內(nèi)容有任何問(wèn)題，歡迎在評(píng)論區(qū)指出。若對(duì)以上內(nèi)容有任何不解，都可私信評(píng)論詢問(wèn)。

🌈諸君，山頂見(jiàn)！