[LeetCode] 260. Single Number III
題目
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.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
直覺解
構想：
紀錄每個數字出現幾次，最後回傳只出現一次的數字。
javascript 實作：
const singleNumber = function(nums) {
if (nums.length === 2) { return nums }
const result = []
const seenNumber = {}
let i = 0
while (i < nums.length) {
seenNumber[nums[i]] ? seenNumber[nums[i]]++ : seenNumber[nums[i]] = 1
i++
}
for (const num in seenNumber) {
if (seenNumber[num] === 1) {
result.push(num)
}
}
return result
}
效能：
Runtime: 88 ms, faster than 54.68% of JavaScript online submissions for Single Number III.
Memory Usage: 42.7 MB, less than 9.36% of JavaScript online submissions for Single Number III.
犯過的低級錯誤：
- 把 seenNumber[num] 寫成 seenNumber.num，而 seenNumber.num 是 undefined
- 把 const num in seenNumber 寫成 const num in nums，結果迭代的 num 變成 nums 的 index
javascript 實作優化：
const singleNumber = function(nums) {
if (nums.length === 2) { return nums }
const result = []
const singleNumber = {}
let i = 0
while (i < nums.length) {
if (singleNumber[nums[i]]) {
delete singleNumber[nums[i]]
} else {
singleNumber[nums[i]] = 1
}
i++
}
for (const num in singleNumber) {
result.push(num)
}
return result
}
效能：
Runtime: 88 ms, faster than 55.94% of JavaScript online submissions for Single Number III.
Memory Usage: 41.6 MB, less than 50.50% of JavaScript online submissions for Single Number III.
研究別人的解
來源：
https://leetcode.com/problems/single-number-iii/discuss/68952/Javascript-solution-using-XOR
別人的 javascript 實作：
var singleNumber = function(nums) {
var res1 = 0,
res2 = 0,
bit;
for(var i = 0; i < nums.length; i++){
res1 ^= nums[i];
}
bit = (res1 & (~ (res1 - 1)));
res1 = 0;
for(i = 0; i < nums.length; i++){
if((nums[i] & bit) === 0)
res1 ^= nums[i];
else
res2 ^= nums[i];
}
return [res1, res2];
};
效能：
Runtime: 76 ms, faster than 97.52% of JavaScript online submissions for Single Number III.
Memory Usage: 39.2 MB, less than 97.52% of JavaScript online submissions for Single Number III.
研究過程：
看起來是用 XOR 把重複出現兩次的數字都互相抵銷變成零，然後想辦法把兩個只出現一次的數字分開。
bit = (res1 & (~ (res1 - 1)));這一段感覺起來，跟 2 補數似乎有關係。説 a 是 b 的 2 補數，意思是，兩者相加後，結果會剛好等於 2。取得 a 的 2 補數的常見方式是，將 a 寫成二進位，把其中的 1 改成 0，0 改成 1，然後再加 1。不過這裡的 ~ (res1 - 1) 則是逆向操作，先減 1 再進行 0、1 反轉，不過我猜意思應該差不多。
將 res1 和 ~ (res1 - 1) 進行 & 運算，我猜，若將結果寫成 2 進位，應該大部分的位元都是 0 ，只有一個位元是 1。若參考另一個解答的說明，這個步驟，跟找出「兩個只出現一次的數字，寫成二進位後，若從最右側開始數，是從哪個位元開始不一樣的」有關。因此，bit 變數若用 2 進位表示，裡面唯一一個是 1 的位元，就是那兩個只出現一次的數字，從右邊開始數，第一個不一樣的位元。
for(i = 0; i < nums.length; i++){
if((nums[i] & bit) === 0)
res1 ^= nums[i];
else
res2 ^= nums[i];
}
所以，這一段的意思是，用「兩個數字第一個不一樣的位元」，把兩個數字分開。能通過 nums[i] & bit) === 0 條件的，是在該位元為 0 的數字；沒辦法通過的，則是在該位元為 1 的數字
參考別人的解，自己用 javascript 實作：
const singleNumber = function(nums) {
if (nums.length === 2) { return nums }
let xor = 0
let num = 0
for (let i = 0; i < nums.length; i++){
xor ^= nums[i]
}
const mask = xor & ((~xor) + 1)
for (i = 0; i < nums.length; i++){
if ((nums[i] & mask) !== 0) {
num ^= nums[i]
}
}
return [num, xor ^ num]
}
效能：
Runtime: 76 ms, faster than 97.52% of JavaScript online submissions for Single Number III.
Memory Usage: 39 MB, less than 98.02% of JavaScript online submissions for Single Number III.
Comments
Post a Comment