Viiisit [LeetCode] - 26. Remove Duplicates from Sorted Array

keep learning, keep coding!

Problem - Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

翻譯蒟蒻

移除 nums 陣列中的相同元素，且要保持元素的相對順序不變，返回獨特元素的數量。

• Example 1:

  Input: nums = [1,1,2]
  Output: 2, nums = [1,2,_]
  Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
  It does not matter what you leave beyond the returned k (hence they are underscores).

• Example 2:

  Input: nums = [0,0,1,1,1,2,2,3,3,4]
  Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
  Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
  It does not matter what you leave beyond the returned k (hence they are underscores).

---

Solution - JavaScript

Solution 1:
(Runtime - 109ms)

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
  for (let i = 0; i < nums.length; i++) {
    // 去比對前後的元素是否一樣
    if (nums[i] === nums[i+1]){
      // 一樣就移除當前元素 
      nums.splice(i, 1)
      // 因為 splice 會改變陣列的長度，因此，i 也要跟著動態更新
      i--;
    }
  }
  return nums.length
};

在迴圈中，使用 splice 函數來移除陣列中的元素時間複雜度高，因為他需要移動元素以填補被刪除的位置，且因為陣列會重新排序，需要考慮如何處理索引，以避免跳過或重複處理某些元素。雖然 splice 函數可以用於在陣列中移除元素，但在某些情況下可能不是最有效的方法。

透過觀察別人的解決方式，使用 two pointer 方法來處理重複元素是更有效的。

Solution 2:
(Runtime - 72ms)

var removeDuplicates = function(nums) {
  // 用於記錄位置
  let position = 0
  for (let i = 1; i < nums.length; i++) {
    // 當有不同元素時，position 就加一，並將不同元素的位置更新到新的位置上
    if (nums[position] !== nums[i]) {
      position++;
      nums[position]=nums[i]
    }
  }
  // 最後要返回 position + 1 是因為陣列的索引從 0 開始，所以 position + 1 為陣列中不同元素的數量。
  return position + 1
};

Two Pointer Concept

方法二使用 position 變數來跟蹤並存儲獨特元素的位置。當找到一個新的獨特元素時，我們將 position 的值增加 1，並將新的獨特元素存儲在 nums[position] 的位置上。因此，position 變數最終指向最後一個獨特元素的位置。所以在返回整個獨特元素的總數量時，要返回 position + 1。

Solution - Ruby

Solution 1:
(Runtime - 69ms)

def remove_duplicates(nums)
  position = 0

  for i in 1..(nums.length - 1)
    if nums[position] != nums[i]
      position += 1
      nums[position] = nums[i]
    end
  end
  position + 1
end

Solution 2:
(Runtime - 63ms)

def remove_duplicates(nums)
  nums.uniq!
  nums.count
end

• uniq! 方法用於刪除陣列中的重複元素並保留原始順序，然後，使用 count 方法計算不重複元素的數量。此會建立一個新的不重複元素的陣列，可能會增加內存使用，而不像方法一在原地修改陣列，並返回不重複元素的數量。

LeetCode 傳送門 - Remove Duplicates from Sorted Array