iT邦幫忙

2021 iThome 鐵人賽

DAY 8
3
Software Development

LeetCode 雙刀流:Python x JavaScript系列 第 8

LeetCode 雙刀流: 26. Remove Duplicates from Sorted Array

  • 分享至 

  • xImage
  •  

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 重新賦值。

反思沉澱

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

舉一反三看看相似題

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


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


上一篇
LeetCode 雙刀流: 412. FizzBuzz
下一篇
從內建容器到善用資料結構特性
系列文
LeetCode 雙刀流:Python x JavaScript30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
TD
iT邦新手 4 級 ‧ 2021-09-23 23:41:50
var removeDuplicates = function(nums) {
     for (i = 0; i < nums.length; i++) {
        if (nums[i] == nums[i+1]) {
            nums.splice(i, 1);
            i--;
        }
    }
    return nums.lengths;
};

最後應該是回傳 nums.length。另一方面,縮排可以稍微調整一下 :)

TD iT邦新手 4 級 ‧ 2021-09-23 23:43:12 檢舉
// usgin object as hashmap

"using" :)

我要留言

立即登入留言