「重複」的判斷是一種常見的的問題,所以我們就選了這個題目 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.
Input: nums = [1,1,2]
Output: 2, nums = [1,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])
}
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)
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;
};
第一個方法是利用下一個元素是否相同來判斷是否重複,其實也可以改成利用前一個元素來判斷。這個方法是往後找,只有找到跟 前一個元素 不重複的時候才需要加入。
count = 0
if nums[i] != nums[i-1]:
nums[count] = nums[i]
count = count + 1
仔細一看,這裡我們用了兩個變數 count 跟 i ,分別指向現在的元素(前一個元素)與下一個元素,用來比較是否不重複,這其實也是一種雙指針(Two Pointers)的概念。
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
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」的資料結構中,都有不重複的性質,因此第三種方法就是利用型態間轉換來達到去除重複的效果。
// 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)
// 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 擔任資料工程師,同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗,持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享,邀請你加入 訂閱 接收最新資訊。
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
。另一方面,縮排可以稍微調整一下 :)
// usgin object as hashmap
"using" :)