LeetCode 在需要接觸演算碼的工程師中，為相當知名的練習場所。當你有需要挑戰自己的腦筋、面試前的準備……等，都滿適合來這邊看一下你的演算法和資料結構的熟悉程度。這回要筆記的有：Remove Duplicates from Sorted Array、 Contains Duplicate 和 Contains Duplicate II。
題目
26. Remove Duplicates from Sorted Array
[連結]：https://leetcode.com/problems/remove-duplicates-from-sorted-array/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
/* 不新增其他的 Array 的情況下： * 1. 運用 Two Pointer 的概念：若 Left === Right ，則用 splice 將其移除，並 i-- (因為陣列長度 - 1) * 2. 承上，如果 Left !== Right，那麼左側的 Index 就以現在跑到的 Index 當做新起點。 */ var removeDuplicates = function(nums) { let leftIndex = 0 for(let i=1; i<nums.length; i++){ if(nums[leftIndex] === nums[i]){ nums.splice(i,1) i-- } if(nums[leftIndex] !== nums[i]){ leftIndex = i } } return leftIndex + 1 }; |
217. Contains Duplicate
[連結]：https://leetcode.com/problems/contains-duplicate/
|
1 2 3 4 5 6 7 |
/* 1. 運用 Set 的資料結構特色，過濾掉重複的元素 * 2. Set.size 取得過濾後的長度，並和原有的陣列作比較，如果小於表示有重複(回傳 true) */ var containsDuplicate = function(nums) { let removeDuplicated = new Set(nums) return removeDuplicated.size < nums.length }; |
219. Contains Duplicate II
[連結]：https://leetcode.com/problems/contains-duplicate-ii/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
/* 運用 Map 的資料結構特色 * 1. 先將特殊情況排除 * 2. 新增一個 map 的資料結構 * 3. 從頭遍歷陣列，如果沒有符合的結果，就將當下數字和對應index存入 map。若有，則將當下的 index 和 儲存在 map 中的 index 相減，看是否在指定範圍內 */ var containsNearbyDuplicate = function(nums, k) { if(nums.length < 1) return false let map = new Map() for(let i=0; i<nums.length;i++){ if( i- map.get(nums[i]) <= k){ return true } map.set(nums[i],i) } return false }; |
