三道【只出現(xiàn)一次的數(shù)】一文輕松搞定！

今天我們來做幾道非常經(jīng)典的題目，第一道題目我們會用多種方法解答，雖然這是一道簡單題目，但是我們學(xué)會了這幾種解題方法，完全可以輕松應(yīng)對后面兩道中等題目。廢話不多說，我們來看題目吧。

為保證嚴(yán)謹(jǐn)性，文章中的所有代碼均經(jīng)過測試，大家可以放心食用

題目來源：leetcode 136只出現(xiàn)一次的數(shù)(簡單)，137只出現(xiàn)一次的數(shù)Ⅱ(中等)260只出現(xiàn)一次的數(shù)Ⅲ(中等)

只出現(xiàn)一次的數(shù)

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

示例 1:

輸入: [2,2,1] 輸出: 1

示例 2:

輸入: [4,1,2,1,2] 輸出: 4

這個題目非常容易理解，就是讓我們找出那個只出現(xiàn)一次的數(shù)字，那么下面我們來看一下這幾種解題方法吧

HashMap

用 HashMap 的這個方法是很容易實(shí)現(xiàn)的，題目要求不是讓我們求次數(shù)嘛，那我們直接遍歷數(shù)組將每個數(shù)字和其出現(xiàn)的次數(shù)存到哈希表里就可以了，然后我們再從哈希表里找出出現(xiàn)一次的那個數(shù)返回即可。

題目代碼

排序搜索法

這個方法也是特別容易想到的，我們首先對數(shù)組進(jìn)行排序，然后遍歷數(shù)組，因?yàn)閿?shù)組中其他數(shù)字都出現(xiàn)兩次，只有目標(biāo)值出現(xiàn)一次，所以則讓我們的指針每次跳兩步，當(dāng)發(fā)現(xiàn)當(dāng)前值和前一位不一樣的情況時，返回前一位即可，當(dāng)然我們需要考慮這種情況，當(dāng)我們的目標(biāo)值出現(xiàn)在數(shù)組最后一位的情況，所以當(dāng)數(shù)組遍歷結(jié)束后沒有返回值，則我們需要返回數(shù)組最后一位，下面我們看一下動圖解析。

題目代碼

這個方法也是比較容易實(shí)現(xiàn)的，我們利用 HashSet 來完成。HashSet 在我們刷題時出現(xiàn)頻率是特別高的,它是基于? HashMap 來實(shí)現(xiàn)的，是一個不允許有重復(fù)元素的集合。那么在這個題解中，它起到什么作用呢？

題目代碼

棧

該方法也很容易想到，我們首先將其排序，然后遍歷數(shù)組，如果棧為空則將當(dāng)前元素壓入棧，如果棧不為空，若當(dāng)前元素和棧頂元素相同則出棧，繼續(xù)遍歷下一元素，如果當(dāng)前元素和棧頂元素不同的話，則說明棧頂元素是只出現(xiàn)一次的元素，我們將其返回即可。這個題目也可以使用隊列做，思路一致，我們就不在這里說明啦。下面我們看下動圖解析。

題目代碼

求和法

這個方法也比較簡單，也是借助咱們的 HashSet 具體思路如下，我們通過 HashSet 保存數(shù)組內(nèi)的元素，然后進(jìn)行求和（setsum），那么得到的這個和則為去除掉重復(fù)元素的和，我們也可以得到所有元素和（numsum）。因?yàn)槲覀兤渌囟汲霈F(xiàn)兩次，僅有一個元素出現(xiàn)一次，那我們通過 setsum * 2 - numsum 得到的元素則為出現(xiàn)一次的數(shù)。

上面我們的 SetSum ?* 2 - NumSum = z 也就是我們所求的值， 是不是感覺很簡單呀。

題目代碼

位運(yùn)算

這個方法主要是借助咱們的位運(yùn)算符 ^ 按位異或，我們先來了解一下這個位運(yùn)算符。

按位異或(XOR)運(yùn)算符“^”是雙目運(yùn)算符。其功能是參與運(yùn)算的兩數(shù)各對應(yīng)的二進(jìn)位相異或，當(dāng)兩數(shù)對應(yīng)的二進(jìn)位相異時，結(jié)果為1。相同時為0。

任何數(shù)和0異或，仍為本身：a⊕0 = a

任何數(shù)和本身異或，為0：a⊕a = 0?

異或運(yùn)算滿足交換律和結(jié)合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

例：

我們通過上面的例子了解了異或運(yùn)算，對應(yīng)位相異時得 1，相同時得 0，那么某個數(shù)跟本身異或時，因?yàn)閷?yīng)位都相同所以結(jié)果為 0 ， 然后異或又滿足交換律和結(jié)合律。則

題目代碼

本題一共介紹了6種解題方法，肯定還有別的方法，歡迎大家討論。大家可以在做題的時候一題多解。這樣能大大提高自己解題能力。下面我們來看一下這些方法如何應(yīng)用到其他題目上。

只出現(xiàn)一次的數(shù)Ⅱ

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

示例 1:

輸入: [2,2,3,2] 輸出: 3

示例 2:

輸入: [0,1,0,1,0,1,99] 輸出: 99

題目很容易理解，剛才的題目是其他元素出現(xiàn)兩次，目標(biāo)元素出現(xiàn)一次，該題是其他元素出現(xiàn)三次，目標(biāo)元素出現(xiàn)一次，所以我們完全可以借助上題的一些做法解決該題。

求和法

我們在上題中介紹了求和法的解題步驟，現(xiàn)在該題中其他元素都出現(xiàn)三次，我們的目標(biāo)元素出現(xiàn)一次，所以我們利用求和法也是完全 OK 的。下面我們來看具體步驟吧。

1.通過遍歷數(shù)組獲取所有元素的和以及 HashSet 內(nèi)元素的和。

2.（SumSet ?* ?3 ?- ?SumNum）/ 2即可，除以 2 是因?yàn)槲覀儨p去之后得到的是 2 倍的目標(biāo)元素。

注：這個題目中需要注意溢出的情況 。

題目代碼

這個題目用 HashMap 和排序查找肯定也是可以的，大家可以自己寫一下，另外我們在第一題中有個利用異或求解的方法，但是這個題目是出現(xiàn)三次，我們則不能利用直接異或來求解，那還有其他方法嗎？

位運(yùn)算

這個方法主要做法是將我們的數(shù)的二進(jìn)制位每一位相加，然后對其每一位的和取余 ，我們看下面的例子。

那么我們?yōu)槭裁匆@樣做呢？大家想一下，如果其他數(shù)都出現(xiàn) 3 次，只有目標(biāo)數(shù)出現(xiàn) 1 次，那么每一位的 1 的個數(shù)無非有這2種情況，為 3 的倍數(shù)（全為出現(xiàn)三次的數(shù)） 或 3 的倍數(shù) +1（包含出現(xiàn)一次的數(shù)）。這個 3 的倍數(shù) +1 的情況也就是我們的目標(biāo)數(shù)的那一位。

題目代碼

? ?

我們來解析一下我們的代碼

<< ? ? 二進(jìn)制左移運(yùn)算符。左操作數(shù)的值向左移動右操作數(shù)指定的位數(shù)。

>> ? ? 二進(jìn)制右移運(yùn)算符。左操作數(shù)的值向右移動右操作數(shù)指定的位數(shù)。

另外我們的代碼中還包含了 a & 1 ?和 ?a | 1 這有什么作用呢？繼續(xù)看下圖

& ? ? ? 按位與運(yùn)算符：參與運(yùn)算的兩個值,如果兩個相應(yīng)位都為1,則該位的結(jié)果為1,否則為0

因?yàn)槲覀?a & 1 中 1 只有最后一位為 1，其余位皆為 0 ，所以我們發(fā)現(xiàn) a & 1的作用就是判斷 a 的最后一位是否為 1 ，如果 a 的最后一位為 1 ，a & 1 = 1,否則為 0 。所以我們還可以通過這個公式來判斷 a 的奇偶性。

| ? ? ? ?按位或運(yùn)算符：只要對應(yīng)的二個二進(jìn)位有一個為1時，結(jié)果位就為1。

這個公式的作用就是將我們移位后的 res 的最后一位 0 變?yōu)?1。這個 1 也就代表著我們只出現(xiàn)一次元素的某一位。

只出現(xiàn)一次的數(shù)Ⅲ

給定一個整數(shù)數(shù)組 nums，其中恰好有兩個元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。找出只出現(xiàn)一次的那兩個元素。

示例 :

輸入: [1,2,1,3,2,5] 輸出: [3,5]

這個也很容易理解，算是對第一題的升級，第一題有 1 個出現(xiàn) 1次的數(shù)，其余出現(xiàn)兩次，這個題目中有 2 個出現(xiàn) 1次的數(shù)，其余數(shù)字出現(xiàn)兩次。那么這個題目我們怎么做呢？我們看一下能不能利用第一題中的做法解決。

HashSet

這個做法和我們第一題的做法一致，只要理解了第一題的做法，這個很容易就能寫出來，有一點(diǎn)不同的是，第一題的 HashSet 里面最后保留了一個元素，該題保留兩個元素。

題目代碼

位運(yùn)算

第一題中，我們可以通過異或運(yùn)算直接求出目標(biāo)數(shù)，但是我們第二題中不能直接用異或，是因?yàn)槠渌麛?shù)字都出現(xiàn)三次，目標(biāo)數(shù)出現(xiàn)一次。在這個題目中其他數(shù)字出現(xiàn)兩次，目標(biāo)數(shù)出現(xiàn)一次，但是這次的目標(biāo)數(shù)為兩個，我們直接異或運(yùn)算的話，得到的數(shù)則為兩個目標(biāo)數(shù)的異或值，那么我們應(yīng)該怎么做呢？

我們試想一下，如果我們先將元素分成兩組，然后每組包含一個目標(biāo)值，那么異或之后，每組得到一個目標(biāo)值，那么我們不就將兩個目標(biāo)值求出了嗎？

例：a,b,a,b,c,d,e,f,e,f ? ? 分組后

A組：a, a , b, b, c ? ? 異或得到 c

B組：e, e, ?f, ?f, ?d ? ? 異或得到 d

原理懂了，那么我們應(yīng)該依據(jù)什么規(guī)則對其進(jìn)行分類呢？

c , d ?兩個不同的數(shù)，那么二進(jìn)制上必定有一位是不同的，那么我們就可以根據(jù)這一位(分組位)來將 c , d 分到兩個組中，數(shù)組中的其他元素，要么在 A 組中，要么在 B 組中。

我們應(yīng)該怎么得到分組位呢？

我們讓 c , d 異或即可，異或運(yùn)算就是對應(yīng)位不同時得 1 ,異或之后值為 1 的其中一位則為我們分組。

例 001 ⊕ ?100 = 101，我們可以用最右邊的 1 或最左邊的 1 做為分組位，數(shù)組元素中，若我們將最右邊的 1 作為我們的分組位，最后一位為 0 的則進(jìn)入 A 組，為 1 的進(jìn)入 B 組。

那么我們應(yīng)該怎么借助分組位進(jìn)行分組呢？

我們處理 c , d 的異或值，可以僅保留異或值的分組位，其余位變?yōu)?0 ，例如 101 變成 001或 100

為什么要這么做呢？在第二題提到，我們可以根據(jù) a & 1 來判斷 a 的最后一位為 0 還是為 1，所以我們將 101 變成 001 之后，然后數(shù)組內(nèi)的元素 ?x & 001 ?即可對 x 進(jìn)行分組 。同樣也可以 x & 100 進(jìn)行分組.

那么我們?nèi)绾尾拍軆H保留分組位，其余位變?yōu)?0 呢？例 101 變?yōu)?001

我們可以利用 x & (-x) 來保留最右邊的 1

題目代碼：