[LeetCode] 137. Single Number II
題目
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- Each element in
numsappears exactly three times except for one element which appears once.
直覺解（失敗）
構想：
模仿 Single Number 那一題，製造一個「出現三次就會歸零」的函式。
javascript 實作：
const singleNumber = function(nums) {
function becomeZeroWhenAppearsThreeTimes (a, b, c) {
return (a | b | c) & (~a | ~b | ~c)
}
let result = nums[0]
for (let i = 1; i < nums.length; i += 2) {
result = becomeZeroWhenAppearsThreeTimes(result, nums[i], nums[i + 1] || 0)
}
return result
}
錯誤：
console.log(singleNumber([0,1,0,1,0,1,99])) // 98 Debug
function dec2bin(dec) {
return (dec >>> 0).toString(2)
}
const singleNumber = function(nums) {
function becomeZeroWhenAppearsThreeTimes (a, b, c) {
return (a | b | c) & (~a | ~b | ~c)
}
let result = nums[0]
for (let i = 1; i < nums.length; i += 2) {
console.log('result:', dec2bin(result))
console.log('nums[i]:', dec2bin(nums[i]))
console.log('nums[i+1]:', dec2bin(nums[i+1]))
result = becomeZeroWhenAppearsThreeTimes(result, nums[i], nums[i + 1] || 0)
console.log(dec2bin(result))
console.log(result)
console.log('-------------')
}
return result
}
const nums = [0,1,0,1,0,1,99]
console.log(singleNumber(nums))
Debug 印出來的東西
result: 0
nums[i]: 1
nums[i+1]: 0
1
1
-------------
result: 1
nums[i]: 1
nums[i+1]: 0
1
1
-------------
result: 1
nums[i]: 1
nums[i+1]: 1100011
1100010
98
-------------
98
解讀 console.log 印出來的結果：becomeZeroWhenAppearsThreeTimes 函式的效果是，對於 a, b, c 轉換成二進制後的每個位元而言，如果三者的值是一樣的，該位元會回傳 0，反之則回傳 1。所以在某個意義上來說，becomeZeroWhenAppearsThreeTimes 函式無法記憶「哪些參數以前出現過」，而只能就當下輸入給他的那三個參數進行判斷。
參考資料
- How do I convert an integer to binary in JavaScript? - stack overflow
研究別人的解
來源：
https://leetcode.com/problems/single-number-ii/discuss/327140/Javascript-beats-97
別人的 javascript 實作：
var singleNumber = function (nums) {
var x1 = 0;
var x2 = 0;
var mask = 0;
for (var i = 0; i < nums.length; i++){
x2 ^= x1 & nums[i];
x1 ^= nums[i];
mask = ~(x1 & x2);
x2 = x2 & mask;
x1 = x1 & mask;
}
return x1;
};
研究過程：
mask = ~(x1 & x2);
x2 = x2 & mask;
x1 = x1 & mask;
根據布林運算的規則，上述這三行的計算結果和底下是一樣的：
const tempX2 = x2
x2 = x2 & ~x1;
x1 = x1 & ~tempX2;
更進一步，可以把 for 迴圈改寫為：
for (var i = 0; i < nums.length; i++){
const tempX2 = x2
x2 = (x2 ^ (x1 & nums[i])) & ~(x1 ^ nums[i])
x1 = (x1 ^ nums[i]) & ~(tempX2 ^ (x1 & nums[i]))
}
把真值表畫出來：
x1 |
x2 |
nums[i] |
新的 x1： |
新的 x2： |
|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
從這張真值表，可以觀察到下列規律：
初始狀態：x1 = 0, x2 = 0
還沒出現第一個 1 的話就維持原狀： x1 = 0, x2 = 0
出現第一個 1： x1 = 1, x2 = 0
還沒出現第二個 1 的話就維持原狀： x1 = 1, x2 = 0
出現第二個 1： x1 = 0, x2 = 1
還沒出現第三個 1 的話就維持原狀： x1 = 0, x2 = 1
出現第三個 1： x1 = 0, x2 = 0
其他觀察： 在計算過程中，不會出現 x1 = 1, x2 = 1 的狀況。所以真值表上 x1 = 1, x2 = 1 的那兩行只是來湊數的。
翻譯得人話一點，意思是：用「x1 = 1, x2 = 0」代表 1 出現一次。用「x1 = 0, x2 = 1」代表 1 出現二次。1 出現第三次的話，就回到初始狀態：「x1 = 0, x2 = 0」。
因為 1 第一次出現時，會紀錄在 x1 裡面，所以 return 時，return x1 就會是答案
我模仿別人的 javascript 實作：
const singleNumber = function(nums) {
let x1 = 0
let x2 = 0
for(var i = 0; i < nums.length; i++){
const tempX2 = x2
x2 = (x1 & ~x2 & nums[i]) | (~x1 & x2 & ~nums[i])
x1 = (x1 & ~tempX2 & ~nums[i]) | (~x1 & ~tempX2 & nums[i])
}
return x1
}
效能：
Runtime: 76 ms, faster than 95.67% of JavaScript online submissions for Single Number II.
Memory Usage: 39.1 MB, less than 90.33% of JavaScript online submissions for Single Number II.
疑問：
- 有一個機械性的方式（disjunctive normal form），可以從真值表倒推回去，找到「如何設定新的 x1 和 x2」。例如，新的 x1 寫成 disjunctive normal form 就會是
(x1 & ~x2 & ~nums[i]) | (~x1 & ~x2 & nums[i])
但作者不是用 disjunctive normal form 的方式找到的，那麼，作者是怎麼找到「如何設定新的 x1 和 x2」的？
參考資料
- Detailed explanation and generalization of the bitwise operation method for single numbers
- A summary: how to use bit manipulation to solve problems easily and efficiently
最後更新日期：2021 年 6 月 1 日
Comments
Post a Comment