[LeetCode] 80. Remove Duplicates from Sorted Array II
題目
Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.
Do not allocate extra space for another array; you must do this by modifying the input array in-place with O(1) extra memory.
直覺解
構想：
宣告兩個指針 filteredNumIndex 和 i，filteredNumIndex指在「出現不超過兩次」的數字上，i 迭代整個 nums 陣列。若迭代到符合「出現不超過兩次」的數字，filteredNumIndex 會把這個數字留下來，反之就不留。
javascript 實作：
const removeDuplicates = function(nums) {
if (nums.length === 1) { return 1 }
let filteredNumIndex = 0
let duplicateCount = 1
let i = 1
while (i < nums.length) {
if (nums[filteredNumIndex] === nums[i]) {
if (duplicateCount < 2) {
filteredNumIndex++
nums[filteredNumIndex] = nums[i]
duplicateCount++
}
} else {
filteredNumIndex++
nums[filteredNumIndex] = nums[i]
duplicateCount = 1
}
i++
}
return filteredNumIndex + 1
}
效能：
Runtime: 88 ms, faster than 76.80% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
Memory Usage: 40.4 MB, less than 66.13% of JavaScript online submissions for Remove Duplicates from Sorted Array II.
犯過的低級錯誤：
- 把 let i = 1 寫成 let i = 0，導致在 input 是 [1] 時，回答長度為 2，nums 此時是 [1, 1]
其他錯誤：
條件順序寫錯，變成每個數字要剛好出現兩次：
const removeDuplicates = function(nums) {
let filteredNumIndex = 0
let = duplicateCount = 1
let i = 1
while (i < nums.length) {
if (duplicateCount < 2) {
if (nums[filteredNumIndex] === nums[i]) {
filteredNumIndex++
nums[filteredNumIndex] = nums[i]
duplicateCount++
}
} else {
if (nums[filteredNumIndex] !== nums[i]) {
filteredNumIndex++
nums[filteredNumIndex] = nums[i]
duplicateCount = 1
}
}
i++
}
return filteredNumIndex + 1
}
Comments
Post a Comment