Leetcode 260 Single Number & bitwise operation
Leetcode 260 題 Single Number III 又是一道只能使用 bitwise operation 才能達到要求的題目，除了需要使用基本的 AND, XOR 之外，還引入了 lowbit function 的概念。
Leetcode 260 — description
Given an integer array
nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
提供一組元素全為「數字」的陣列，其中「只有兩個」元素是唯一存在，其他元素「都會重複兩次」。
如果要達到任務，在時間複雜度 O(N)、空間複雜度 O(N) 的要求下其實不難，但偏偏題目要求時間複雜度 O(N)，然後空間複雜度要 O(1)。
在不能增加空間來儲存元素的額外資訊（譬如出現次數，或有沒有看過）的情況下，一時想到能做的，只有透過修改元素值來當作標記，通常的做法是將正數改為負數，但這題有趣的是，題目提供的陣列當中，數字包含負數，所以類似下面這種做法就完全行不通：
let result = []
for (let i = 0; i < nums.length; i++){
let index = Math.abs(nums[i]) - 1
if (nums[index] < 0) {
result.push(index + 1)
} else {
nums[index] = -nums[index]
}
}也無法使用 Cyclic sort 或類似的方法。我想破頭也想不出來，只好求教於他人的解法了。
Solution with O(1) space complexity
廢話不說，直接呈上解法
var singleNumber = function(nums) {
let xor = 0
for (let i = 0; i < nums.length; i++) {
xor ^= nums[i]
}
xor &= -xor let result = [[],[]]
for (let i = 0; i < nums.length; i++) {
if ((xor & nums[i]) === 0 ) {
result[0] ^= nums[i]
} else {
result[1] ^= nums[i]
}
} return result
}
第一次看到這個解法，完全不知道在幹嘛，花了一些時間才慢慢釐清脈絡。接下來，我希望能夠用我自己的方法說明，讓讀者有機會更容易瞭解這個解法。
Solution — core concepts
首先，先說明一下這個解法核心概念
- 找到一種「連續運算」方法，能讓重複出現 2 次的數字自己消失，所以剩下來的就只會是那兩個只出現 1 次的數字的運算結果。（所以會發現，其實局限性很高）
- 不過只有上面那個方法還不夠，因為我們只會拿到運算結果，而不是分開的兩個數字。因此，我們需要有另外一個方法，來區隔那兩個數字
1) 連續運算，消除重複出現的數字
關於第一點，也許第一時間會想到數學上的減法，但實際上是行不通的。舉例來說：
[1,2,1,3,2,5]1 - 2 - 1 - 3 - 2 - 5 不會等於 3 - 5
而我們需要找的是一種運算，如果假設它叫做 “@”，會達成以下結果
1 @ 2 @ 1 @ 3 @ 2 @ 5 正好等於 3 @ 5在 bitwise 的運算當中，XOR 完美地展現這個特性。以剛剛的例子來看：
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 // 得到 6，或二進位的 110
3 ^ 5 // 得到 6，或二進位的 110也就是解法前半部在做的事情
var singleNumber = function(nums) {
let xor = 0
for (let i = 0; i < nums.length; i++) {
xor ^= nums[i]
} ...
}
2) 區隔不同數字
回到剛剛的例子，先假設我們已經知道我們要找的數字是 3 和 5，接下來，我們想個辦法分辨出這兩個數字，從二進位的角度來看，3 和 5 分別是
011 // 二進位的 3
101 // 二進位的 5觀察一下，兩者第一個 bit 的值都相同，而第二個和第三個 bit 的值不同。雖然我們可以直接去比較所有的 bit，但我們也可以只比較「第一個出現差異的 bit」，也就是第二個 bit 的值，就知道兩者的不同。
所以接下來的想法是，我們只要找到一個合適的遮罩 (mask)，當這兩個數跟這個遮罩進行運算的時候，確定會得到不同的結果。
但其實，拿隨便一個數字，都會得到不同的結果，另一個更糟糕的是，其實我們也不知道不同的結果是什麼，所以沒辦法設定條件去做區分。
因此，這裡我們要限縮目標，也就是
找到一個合適的遮罩 (mask)，當這兩個數跟這個遮罩進行運算的時候，其中一個得到的答案會是 0
如果找到的話，我們就可以建立下面這樣的判斷式
if ( arr[i] do something with someone === 0) {
...
} else {
...
}透過運算結果，區分兩個數字，並丟到不同的地方去處理。
現在我們知道要往哪個方向走了，回顧一下剛走完第一步的狀況，現在我們手上有兩筆資訊
- 把所有元素透過 XOR 運算完的結果（以上帝視角來看就是 3 ^ 5）
- 原陣列當中的所有元素
接下來，就是要想辦法找到那個可以區隔兩個數字的遮罩！
Mask & lowbit function
Lowbit function 在做的事情是：找到第一個（最低位）bit 不為 0 的位置。舉例來說
0000 // 得到 0
0010 // 得到 10
0011 // 得到 1
0100 // 得到 100
0101 // 得到 1
0110 // 得到 10
0111 // 得到 1
1000 // 得到 1000這對我們來說有什麼幫助呢？如果回到剛剛的 3 和 5 的例子，我們已經知道他們最低的差異點在第二個 bit，所以如果我們分別拿 3 和 5 跟二進位的 0010 來做 AND 運算，就會得到：
011 & 010 // 得到 010
101 & 010 // 得到 000會發現得到我們之前想要的結果，也就是
- 找到一個遮罩，分別和兩個數字運算過後，確定會得到不同的結果
- 其中一個的結果會是 0
換另外一個例子，假設是 7 和 28，兩者最低的差異點在第一個 bit，所以遮罩是 1，運算如下：
00111 & 00001 // 得到 00001
11100 & 00001 // 得到 00000同樣會得到不同的結果，且其中一個結果是 0。
那麼，最後一個問題就是，我們要怎麼算出遮罩呢？其實我們已經有 XOR 的結果了，這個結果告訴我們「兩個數字相比，有不同值的 bit 的位置」，舉例來說
011 ^ 101 // 得到 110
00101 ^ 11100 // 得到 11001 不過我們其實只要最低位差異就行，也就是最低位的 1（第一次出現 1 的地方）就行，這時候就可以靠剛剛提到的 lowbit function 來幫我們取出來
Lowbit function 出奇的簡單：
function lowbit (x) {
return x & (-x)
}二進位的負數表示法是以補數的方式呈現，根據 wiki 的說明 ：
二補數（英語：2’s complement）是一種用二進位表示有號數的方法，也是一種將數字的正負號變號的方式，常在電腦科學中使用。二補數以有符號位元的二進位數定義。
正數和 0的二補數就是該數字本身。負數的二補數則是將其對應正數按位元取反再加1。
舉例來說如下
2 // 00000010
-2 // 11111110
3 // 00000011
-3 // 11111101
4 // 00000100
-4 // 11111100
5 // 00000101
-5 // 11111011然後很神奇的，只要把數字取負數之後，再來個 AND，就可以得到最低位的差異的 bit，譬如
2 & -2 // 得到 0010，也就是二進位當中的 2(0010) 第一個不為 0 的值
3 & -3 // 得到 0001，也就是二進位當中的 3(0011) 第一個不為 0 的值
4 & -4 // 得到 0100，也就是二進位當中的 4(0100) 第一個不為 0 的值
5 & -5 // 得到 0001，也就是二進位當中的 5(0101) 第一個不為 0 的值Solution — step by step
上面提到了解題的核心概念，以及介紹需要使用的工具，最後我們再來看一次解法，並逐步詳細解說
var singleNumber = function(nums) {
let xor = 0
for (let i = 0; i < nums.length; i++) {
xor ^= nums[i]
}
xor &= -xorlet result = [[],[]]
for (let i = 0; i < nums.length; i++) {
if ((xor & nums[i]) === 0 ) {
result[0] ^= nums[i]
} else {
result[1] ^= nums[i]
}
}return result
}// example
let nums = [1,2,1,3,2,5]
singleNumber(nums)
- 首先，將所有元素進行 XOR 的運算，所以最後會得到等同於 3 ^ 5 的結果，也就是
110，存放在變數XOR當中。 - 接這，利用 lowbit function 建立遮罩，這裡會得到結果
010，並存放在變數XOR當中。 - 建立儲存最後結果的變數。已知只有兩個結果，所以直接建立帶有兩個元素的陣列（這裡其實不一定要這麼做）
- 最後，再次跑過所有元素，並用遮罩來區個數字。這裡我們就直接列舉
xor 為 101a[0] 為 1，二進位為 001，001 & 010 為 000
a[1] 為 2，二進位為 010，010 & 010 為 010
a[2] 為 1，二進位為 001，001 & 010 為 000
a[3] 為 3，二進位為 011，011 & 010 為 010
a[4] 為 2，二進位為 010，010 & 010 為 010
a[5] 為 5，二進位為 101，101 & 010 為 000
這時候就會發現，數字 1, 5 會滿足 (xor & nums[i]) === 0 條件進入 result[0] ^= nums[i] 當中，而 2, 3 會進入另外一邊。
分開之後，接下來做的事情，其實就跟第一步完全一樣， 所以result[0] 和 result[1] 的結果分別是
result[0] 等於 1 ^ 1 ^ 5 等於 5
result[1] 等於 2 ^ 2 ^ 3 等於 3因為最後得到的結果就是 [5 ,3]
也因為這樣的作法無法產出有序的陣列結果，所以題目不要求產出的陣列元素順序。反過來說，其實題目是為了這樣的特殊解法，而特別設計這麼多的限制條件。
在 Leetcode 上常常會看到特殊的題目與解法，有時候可能會覺得這在工作上一點用也沒有。不過就當作是個有趣的發現，也許哪天，這個發現會在意想不到的地方，用截然不同的形式浮上腦海。
About me
Self-taught and trained in software development knowledge and skills, I am passionate about creating changes through technology.
Find more at Github, LinkedIn, Teaching at ALPHA Camp
