26. Remove Duplicates from Sorted Array

「重複」的判斷是一種常見的的問題，所以我們就選了這個題目 26. 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.

再搭配範例理解題目

• Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]

• Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]

該題目會給予一個「由小到大排序過」的陣列，要求在「同一個陣列中」，把重複的部分拿掉、不重複的元素往左移，剩下右邊多餘的來位置不計算。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：暴力法

第一個直覺的想法是利用其「排序過」的特性，利用隔壁的元素進行判斷是否重複。這種方法可以利用 下一個元素 是否相同，若相同的話需要移除。

if nums[i] == nums[i+1]:
    nums.remove(nums[i])
}

那我們先用 Python 實作看看

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        while i < len(nums)-1:
            if nums[i] == nums[i+1]:
                nums.remove(nums[i])
                i -= 1
            i += 1
            
        return len(nums)

也可以用 JavaScript 復刻一次

var removeDuplicates = function(nums) {
  for (i = 0; i < nums.length; i++) {
    if (nums[i] == nums[i+1]) {
      nums.splice(i, 1);
      i--;
    }
  }
  return nums.length;
};

方法 ②：雙指針（Two Pointers）

第一個方法是利用下一個元素是否相同來判斷是否重複，其實也可以改成利用前一個元素來判斷。這個方法是往後找，只有找到跟 前一個元素 不重複的時候才需要加入。

count = 0
if nums[i] != nums[i-1]:
    nums[count] = nums[i]
    count = count + 1

仔細一看，這裡我們用了兩個變數 count 跟 i ，分別指向現在的元素（前一個元素）與下一個元素，用來比較是否不重複，這其實也是一種雙指針（Two Pointers）的概念。

那我們先用 Python 實作看看

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        
        count = 1
        for i in range(1, len(nums)):
            if (nums[i] != nums[i-1]):
                nums[count] = nums[i]
                count += 1
        
        return count

也可以用 JavaScript 復刻一次

var removeDuplicates = function(nums) {   
  var count = 1;
  for(var i = 1 ; i < nums.length ; i++){
    if(nums[i] != nums[i-1]){
      nums[count] = nums[i];
      count++;
    }
  } 
  return count;
};

方法 ③：其他資料結構

講到「重複」、「去除重複」類似的關鍵字，除了使用邏輯或流程的方法進行判斷，也可以利用「資料結構」的特性。舉例而言，在「Set」或「Map」的資料結構中，都有不重複的性質，因此第三種方法就是利用型態間轉換來達到去除重複的效果。

那我們先用 Python 實作看看

// using dict as hashmap
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int: 
        map = {}
        for num in nums:
          map[num] = 1   
        nums = list(map.keys())
        return len(nums)

// set
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        nums = set(nums)
        return len(nums)

也可以用 JavaScript 復刻一次

// usgin object as hashmap
var removeDuplicates = function(nums) {
    map = {}
    for(let num of nums){
      map[num] = 1
    }
    nums = Object.keys(map);
    return nums.length;
};

// map
var removeDuplicates = function(nums) {
    map = new Map()
    for(let num of nums){
      map.set(num, 1);
    }
    nums = Array.from(map.keys());
    return nums.length;
};

// set
var removeDuplicates = function(nums) {
    nums = [...new Set(nums)];
    return nums.length;
};

雖然這幾種資料結構執行的結果可以滿足題目的要求，但實際上是過不了測試的。主要的原因在於題目的描述中有一句話：「remove the duplicates in-place such that each unique element appears only once」，當中的 in-place 的意思是 不能更動到原有陣列的起始位置 ，也就是說不能對 nums 重新賦值。

反思沉澱

重複的判斷是一種常見的的問題，透過這個題目我們嘗試「邏輯與流程控制」與「善用資料結構特性」兩種方法來實現。雖然本題有一些限制必須一定要用「邏輯與流程控制」，但實務上「善用資料結構特性」也是一種可行的路。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 27. Remove Element
• 80. Remove Duplicates from Sorted Array II
• 442. Find All Duplicates in an Array
• 83. Remove Duplicates from Sorted List
• 82. Remove Duplicates from Sorted List II

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。