【LeetCode】 移除元素 - 雙指標 - 快慢指標 - 對撞指標

語言: CN / TW / HK

theme: cyanosis highlight: a11y-dark


小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

今天再來一個簡單題,刷爆他~

27. 移除元素【簡單】

https://leetcode-cn.com/problems/remove-element/

給你一個數組 nums 和一個值 val,你需要 原地 移除所有數值等於 val 的元素,並返回移除後陣列的新長度。
不要使用額外的陣列空間,你必須僅使用 O(1) 額外空間並 原地 修改輸入陣列。
元素的順序可以改變。你不需要考慮陣列中超出新長度後面的元素。

【解法】快慢指標

刪除有序陣列中的重複項的思路一樣,快指標i用來遍歷一遍nums,慢指標j用來維持陣列【不包含val元素】 - 【注意】這題判斷語句內部的執行順序與26題不一樣,先進行賦值再自增 - 【注意】由於後自增,所以最後返回值已不需要手動+1

javascript /** * @param {number[]} nums * @param {number} val * @return {number} */ var removeElement = function(nums, val) { let j = 0; for(let i = 0; i< nums.length; i++){ if(nums[i] !== val){ nums[j] = nums[i]; j++; } } return j; }; 在這裡插入圖片描述

【解法二】對撞指標

由於題目對元素順序沒有要求,所以可以在碰到需要捨棄的元素(等於val的元素)時,用最後的元素替代即可

定義左右兩個對撞指標

javascript var removeElement = function(nums, val) { let left = 0; let right = nums.length - 1; while (left <= right) { if (nums[left] === val) { nums[left] = nums[right]; right--; } else { left++; } } return left; }; 在這裡插入圖片描述

「其他文章」