Halo，這里是Ppeua。平時主要更新C語言，C++，數(shù)據(jù)結構算法......感興趣就關注我吧！你定不會失望。

?

🌈個人主頁：主頁鏈接

🌈算法專欄：專欄鏈接

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

🌈LeetCode專欄：專欄鏈接?

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

🌈代碼倉庫：Gitee鏈接

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

?

目錄

先來了解一下異或^:

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

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

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

完結撒花：

---

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

先來了解一下異或^:

相同為0,不同則為1,這是在二進制編碼中

101111^10111=000001010^0101=1111

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

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

x^x=0
x^0=x

?此外 ,異或滿足結合律與交換律

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

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

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

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

你必須設計并實現(xiàn)線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間。

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

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

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

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

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

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

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

你必須設計并實現(xiàn)線性時間復雜度的算法且不使用額外空間來解決此問題。

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

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

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

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

若總數(shù)不為3的倍數(shù)，則說明該位上有唯一出現(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

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

你必須設計并實現(xiàn)線性時間復雜度的算法且僅使用常量額外空間來解決此問題。

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

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

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

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

那么如何將兩個數(shù)字分開放呢??

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

?

先將所有數(shù)據(jù)^,因為除這兩個數(shù)字外,其余都是兩兩出現(xiàn),^后的結果為這兩個數(shù)字的結果.

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

在進行一個循環(huán)將每一個數(shù)與這個數(shù),無非就兩種結果,將這兩種結果分組,即可

#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;}
};

完結撒花：

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

🌈若對你有些許幫助，可以點贊、關注、評論支持下博主，你的支持將是我前進路上最大的動力。

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

🌈諸君，山頂見！