[LeetCode] #26. Remove Duplicates from Sorted Array

題目

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns 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.

直覺解

構想：

從 nums 的最後一個元素開始檢查，如果他和前一個元素相同的話，就把當下這個元素刪掉。最後回傳 nums.length

javascript 實作：

const removeDuplicates = function(nums) {

      for (let i = nums.length - 1; i > 0; i--) {

          if (nums[i] === nums[i - 1]) {

              nums.splice(i, 1)

          }

      }

      return nums.length

}

效能：

Runtime: 100 ms, faster than 49.12% of JavaScript online submissions for Find Words That Can Be Formed by Characters.
Memory Usage: 40.8 MB, less than 75.80% of JavaScript online submissions for Find Words That Can Be Formed by Characters.

看 Solution 的解

構想：

使用 i, j 兩個 pointer，i 負責指在沒有重複的數字上，j 則迭代 nums 中的每個元素。如果 j 有發現下一個不重複的數字，就把 i 的下一個數字改成「j 發現的那個數字」

javascript 實作：

const removeDuplicates = function(nums) {

      let i = 0

      for (let j = 1; j < nums.length; j++) {

          if (nums[i] !== nums[j]) {

              i++

              nums[i] = nums[j]

          }

      }

      return i + 1

}

效能：

Runtime: 92 ms, faster than 78.54% of JavaScript online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 41.2 MB, less than 27.51% of JavaScript online submissions for Remove Duplicates from Sorted Array.

犯過的低級錯誤：

• 把 nums[i] = nums[j] 寫成 nums[i] === nums[j]