[LeetCode] #287. Find the Duplicate Number
題目
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
直覺解（未讀懂題目版）
構想：
計算出「1 + 2 + ... + (nums.length - 1)」的總和，再計算出 nums 中每個元素的總和，然後用後者減去前者，就能得到答案
javascript 實作：
const findDuplicate = function(nums) {
if (nums.length === 2) { return nums[0] }
const factorial = (nums.length * (nums.length - 1) / 2)
const reducer = (accumulator, currentValue) => accumulator + currentValue
const sum = nums.reduce(reducer)
const repeatedNumber = sum - factorial
return repeatedNumber
}
錯誤：
重複的那個數字，出現次數可能不只二次，所以這個方法不可行。
直覺解（已讀懂題目版，未挑戰 Follow up）
構想：
用 nums 紀錄數字是否出現過：迭代 nums 中的每個元素，如果當下的元素是 2 ，就用 nums 中第二個元素的值的正負號，紀錄 2 是否出現過。正的代表沒出現過，負的代表有出現過。（不符合「without modifying the array」的限制）
例如，nums = [1, 3, 4, 2, 2]| nums 的每個元素 | 1 | 3 | 4 | 2 | 2 |
| 元素的 index | 0 | 1 | 2 | 3 | 4 |
| 記錄的對象 | 1 | 2 | 3 | 4 | 5 |
依序迭代 nums 中每個元素，首先是 1：「記錄的對象」是 1 的那一格，對應的元素剛好是 1，所以把那一格的值改成負數：
| nums 的每個元素 | -1 | 3 | 4 | 2 | 2 |
| 元素的 index | 0 | 1 | 2 | 3 | 4 |
| 記錄的對象 | 1 | 2 | 3 | 4 | 5 |
依序迭代 nums 中每個元素，接下來輪到 3：「記錄的對象」是 3 的那一格，對應的元素剛好是 4，所以把那一格的值改成負數：
| nums 的每個元素 | -1 | 3 | -4 | 2 | 2 |
| 元素的 index | 0 | 1 | 2 | 3 | 4 |
| 記錄的對象 | 1 | 2 | 3 | 4 | 5 |
依序迭代 nums 中每個元素，接下來輪到 4：「記錄的對象」是 4 的那一格，對應的元素剛好是 2，所以把那一格的值改成負數：
| nums 的每個元素 | -1 | 3 | -4 | -2 | 2 |
| 元素的 index | 0 | 1 | 2 | 3 | 4 |
| 記錄的對象 | 1 | 2 | 3 | 4 | 5 |
依序迭代 nums 中每個元素，接下來輪到 2：「記錄的對象」是 2 的那一格，對應的元素剛好是 3，所以把那一格的值改成負數：
| nums 的每個元素 | -1 | -3 | -4 | -2 | 2 |
| 元素的 index | 0 | 1 | 2 | 3 | 4 |
| 記錄的對象 | 1 | 2 | 3 | 4 | 5 |
依序迭代 nums 中每個元素，接下來輪到 2：「記錄的對象」是 2 的那一格，對應的元素剛好是 -3，是負數，代表現在這個 2 是重複的
javascript 實作：
const findDuplicate = function(nums) {
for (let i = 0; i < nums.length; i++) {
if (nums[Math.abs(nums[i]) - 1] > 0) {
nums[Math.abs(nums[i]) - 1] *= -1
} else {
return Math.abs(nums[i])
}
}
}
效能：
Runtime: 100 ms, faster than 22.86% of JavaScript online submissions for
Find the Duplicate Number.
Memory Usage: 48.2 MB, less than 12.91% of JavaScript online submissions for
Find the Duplicate Number.
犯過的沒營養錯誤：
- 把 index 寫成 Math.abs(nums[i] - 1)，減 1 之後才取絕對值，導致計算出來的 index 超出 nums 陣列的範圍，取出來的值變成 undefined
Link list 解（觀摩討論學到的方法）
構想：
用 nums 中 index 為 0 的元素當作 head，link list 中第二個元素則是 nums[head]。得到 link list 中下一個元素的方式，就是 nums[link list 目前的最後一個元素]
例如，nums = [1, 3, 4, 2, 2]，得到的 link list 是：
1 → 3 → 2 → 4
↑ |
-----
階段一：用快慢指針，快的每次跑兩步，慢的每次跑一步，兩個指針停在同一個地方時停下來。
階段二：將其中一個指針歸零，然後兩個指針每次都只跑一步，當兩個指針再次停在同一個地方，那個地方就是重複的數字。
javascript 實作：
const findDuplicate = function(nums) {
let slow = nums[0]
let fast = nums[nums[0]]
while (slow !== fast) {
slow = nums[slow]
fast = nums[nums[fast]]
}
fast = nums[0]
slow = nums[slow]
while (slow !== fast) {
slow = nums[slow]
fast = nums[fast]
}
return slow
}
效能：
Runtime: 88 ms, faster than 41.15% of JavaScript online submissions for Find the Duplicate Number.
Memory Usage: 47.9 MB, less than 15.79% of JavaScript online submissions for Find the Duplicate Number.
不明白的地方：
- 階段一：如何確定「快指針跑兩步，慢指針跑一步」時，最後一定會在同一個地方停下來，而不會總是擦身而過？
- 階段二：為什麼最後快慢指針同時停留的那個地方，能夠保證一定是重複的數字？
參考資料：
研究別人的解
來源：Alpha Camp LeetCode 訓練營講師 Wesley 介紹的其中一個解
講師的講義：
Constant space : binary search
- 全部 100 個數字 值域 1-99 中間值 (1+99)/2 = 50
- start = 0, end = 99, 0 < n <= 99
- 對於全部100個數字， count = "有幾個數字超過50"?
- 1-99不重複的話，應該有 99-50=49 個數字超過 50 ，但今天有一個重複
- 若 count > 49 : 表示我們的目標在後面這半，
- start = mid
- 若 count <= 49 : 表示目標在前面一半
- end = mid
- 重複直到夾擊範圍只有一個數字就是答案 (end = start + 1)
- (同學提供) 重複直到範圍剩下少量數字以 for loop 解開
別人的 python 3 實作版本一：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
start = 0
end = len(nums) - 1
while start + 1 < end :
mid = (end + start + 1) // 2
count = 0
for num in nums:
if mid < num <= end :
count += 1
if count > end - mid:
start = mid
else :
end = mid
return end
效能：
Runtime: 1101 ms, faster than 5.44% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 28.2 MB, less than 33.07% of Python3 online submissions for Find the Duplicate Number.
別人的 python 3 實作版本二：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
start = 0
end = len(nums) - 1
while start + 1 < end :
mid = (end + start + 1) // 2
count = 0
for num in nums:
if start < num <= mid :
count += 1
if count > mid - start:
end = mid
else :
start = mid
return start + 1
效能：
Runtime: 956 ms, faster than 12.61% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 28.2 MB, less than 50.89% of Python3 online submissions for Find the Duplicate Number.
研究感想：
版本一，是數 nums 裡面有多少數字在 (mid, end]這個區間裡；版本二，是數 nums 裡面有多少數字在 (star, mid]這個區間裡。
為了一窺 while 迴圈停止條件的奧秘，我試著寫了自己的版本：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
start = 1
end = len(nums) - 1
while start < end:
mid = (start + end) // 2
count = 0
for num in nums:
if start <= num <= mid:
count += 1
if count == mid - start + 1:
start = mid + 1
else:
end = mid
return end
Wrong Answer
Input: [2,2,2,2,2]
Output: 1
Expected: 2
判斷去左邊或去右邊的條件寫錯了，造成誤判。改良如下（最後 start 會等於 end，所以 return start 也是可以的）：
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
start = 1
end = len(nums) - 1
while start < end:
mid = (start + end) // 2
count = 0
for num in nums:
if start <= num <= mid:
count += 1
if count <= mid - start + 1:
start = mid + 1
else:
end = mid
return end
效能：
Runtime: 1324 ms, faster than 5.04% of Python3 online submissions for Find the Duplicate Number.
Memory Usage: 27.9 MB, less than 93.47% of Python3 online submissions for Find the Duplicate Number.
最後更新日期：2021 年 9 月 2 日
Comments
Post a Comment