題目27. 移除元素 - 力扣LeetCode給你一個(gè)數(shù)組nums和一個(gè)值val你需要原地移除所有數(shù)值等于val的元素。元素的順序可能發(fā)生改變。然后返回nums中與val不同的元素的數(shù)量。假設(shè)nums中不等于val的元素?cái)?shù)量為k要通過(guò)此題您需要執(zhí)行以下操作更改nums數(shù)組使nums的前k個(gè)元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回k。示例 1輸入nums [3,2,2,3], val 3輸出2, nums [2,2,,]解釋你的函數(shù)應(yīng)該返回 k 2, 并且 nums 中的前兩個(gè)元素均為 2。你在返回的 k 個(gè)元素之外留下了什么并不重要因此它們并不計(jì)入評(píng)測(cè)。示例 2輸入nums [0,1,2,2,3,0,4,2], val 2輸出5, nums [0,1,4,0,3,,,_]解釋你的函數(shù)應(yīng)該返回 k 5并且 nums 中的前五個(gè)元素為 0,0,1,3,4。注意這五個(gè)元素可以任意順序返回。你在返回的 k 個(gè)元素之外留下了什么并不重要因此它們并不計(jì)入評(píng)測(cè)。提示0 nums.length 1000 nums[i] 500 val 100題解解題思路方法雙指針快慢指針時(shí)間復(fù)雜度: O(n)空間復(fù)雜度: O(1)前提理解題目要求原地移除也就是說(shuō)不能另外開(kāi)一個(gè)新數(shù)組把要保留的元素裝進(jìn)去只能在原來(lái)的數(shù)組nums上動(dòng)手。移除的本質(zhì)是把要保留的元素往前搬覆蓋掉要?jiǎng)h除的元素然后返回新的長(zhǎng)度搬完之后后面多出來(lái)的那部分元素是什么并不重要過(guò)程定義慢指針slow它指向新數(shù)組里下一個(gè)要填充的位置初始為 0。同時(shí)它也可以理解為當(dāng)前已經(jīng)保留的元素個(gè)數(shù)定義快指針fast它負(fù)責(zé)從頭到尾掃描整個(gè)原數(shù)組初始也為 0讓快指針不斷向數(shù)組的右邊前進(jìn)可以使用for循環(huán)當(dāng)循環(huán)結(jié)束時(shí)說(shuō)明整個(gè)數(shù)組已經(jīng)遍歷完直接返回slow即數(shù)組長(zhǎng)度程序結(jié)束每進(jìn)入一個(gè)循環(huán)都要進(jìn)行以下判斷nums[fast] ! val //val為要?jiǎng)h除的目標(biāo)值說(shuō)明快指針fast所指的這個(gè)元素不是目標(biāo)值val需要保留如何保留呢把它搬到慢指針?biāo)诘奈恢眉磏ums[slow] nums[fast]然后慢指針后移一位slow不符合上面的條件直接印證快指針fast所對(duì)應(yīng)的值剛好為目標(biāo)值val這個(gè)時(shí)候快指針fast直接前進(jìn)而慢指針slow不變這樣如果有下一次循環(huán)則快指針fast所對(duì)應(yīng)的值直接賦值給慢指針fast所對(duì)應(yīng)的值剛好完成刪除數(shù)組元素。循環(huán)結(jié)束時(shí)slow的值正好就是與val不同的元素?cái)?shù)量也就是題目要返回的k同時(shí)可以說(shuō)是新數(shù)組的長(zhǎng)度。補(bǔ)充方法相向雙指針頭尾指針如果數(shù)組中等于val的元素很少可以讓左右指針從兩端往中間夾右指針指向還沒(méi)處理的那部分的末尾當(dāng)nums[left] val時(shí)就用nums[right]即右邊沒(méi)有問(wèn)題的元素把這個(gè)位置等于val的元素覆蓋掉然后right--否則left。它的思想是用尾部不需要保留的元素來(lái)填前面的坑能少搬一些元素缺點(diǎn)是會(huì)打亂元素的相對(duì)順序圖解代碼實(shí)現(xiàn)偽代碼slow 0 for fast 0 to nums.size - 1 { if nums[fast] ! val nums[slow] nums[fast] slow } return slowJava實(shí)現(xiàn)class Solution { public int removeElement(int[] nums, int val) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; } }C語(yǔ)言實(shí)現(xiàn)int removeElement(int* nums, int numsSize, int val) { int slow 0; for (int fast 0; fast numsSize; fast){ if (nums[fast] ! val){ nums[slow] nums[fast]; slow; } } return slow; }Python實(shí)現(xiàn)from typing import List class Solution: def removeElement(self, nums: List[int], val: int) - int: slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow參考代碼隨想錄力扣官方題解題目頁(yè)里的題解區(qū)可以對(duì)照快慢指針和相向雙指針兩種寫(xiě)法OI Wiki算法競(jìng)賽向的知識(shí)庫(kù)雙指針、二分等專(zhuān)題都有Hello 算法開(kāi)源算法教程同一份代碼有 Java / C / Python 三個(gè)版本