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