[LeetCode] 136. Single Number
題目
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- Each element in the array appears twice except for one element which appears only once.
直覺解
構想：
迭代整個陣列，紀錄每個數字出現幾次。最後從記錄裡找出只出現一次的數字。
javascript 實作：
const singleNumber = function(nums) {
const countNumber = {}
let i = 0
while(i < nums.length) {
if (!countNumber[nums[i]]) {
countNumber[nums[i]] = 1
} else {
countNumber[nums[i]] ++
}
i++
}
i = 0
while(i < nums.length) {
if (countNumber[nums[i]] === 1) {
return nums[i]
}
i++
}
}
效能：
Runtime: 100 ms, faster than 37.71% of JavaScript online submissions for Single Number.
Memory Usage: 42.3 MB, less than 54.70% of JavaScript online submissions for Single Number.
犯過的低級錯誤：
- 把 i = 0 寫成 let i = 0，導致重複宣告 i
[Solution] approach 1: List operation
構想：
宣告一個陣列 A。迭代 nums 陣列，如果該數字不在 A 裡面，就放進 A，已經在 A 裡面，就把他從 A 裡面刪掉。最後 A 裡面只剩下出現一次的數字。
javascript 實作：
const singleNumber = function(nums) {
const singleNumber = []
let i = 0
while (i < nums.length) {
const index = singleNumber.indexOf(nums[i])
if (index >= 0) {
singleNumber.splice(index, 1)
} else {
singleNumber.push(nums[i])
}
i++
}
return singleNumber[0]
}
效能：
Runtime: 216 ms, faster than 15.39% of JavaScript online submissions for Single Number.
Memory Usage: 42.5 MB, less than 53.07% of JavaScript online submissions for Single Number.
犯過的低級錯誤：
- 把 singleNumber.indexOf(nums[i]) 寫成 singleNumber.indexOf[nums[i]]，導致算出來的結果永遠是 undefined
[Solution] approach 3: Math
構想：
用 seenNumbers 陣列紀錄 nums 中出現過的數字，重複出現的只計算一次。例如，如果 nums = [2, 2, 1]，則 seenNumbers 就會是 [2, 1]。seenNumbers 的總和 * 2 減掉 nums 的總和，就是答案
javascript 實作：
const singleNumber = function(nums) {
const seenNumbers = []
let sumOfSeenNumbers = 0
let sumOfNums = 0
let i = 0
while (i < nums.length) {
const index = seenNumbers.indexOf(nums[i])
if (index < 0) {
seenNumbers.push(nums[i])
sumOfSeenNumbers += nums[i]
}
sumOfNums += nums[i]
i++
}
return sumOfSeenNumbers * 2 - sumOfNums
}
效能：
Runtime: 296 ms, faster than 12.65% of JavaScript online submissions for Single Number.
Memory Usage: 41 MB, less than 74.47% of JavaScript online submissions for Single Number.
[Solution] approach 4: Bit Manipulation
構想：
相同的數字，經過 XOR 運算後會被抵消變成 0。最後沒被抵消成功的，就是只出現一次的數字
javascript 實作：
const singleNumber = function(nums) {
for (let i = 1; i < nums.length; i++) {
nums[0] = nums[0] ^ nums[i]
}
return nums[0]
}
效能：
Runtime: 80 ms, faster than 92.53% of JavaScript online submissions for Single Number.
Memory Usage: 39.9 MB, less than 98.82% of JavaScript online submissions for Single Number.
Comments
Post a Comment