27. 移除元素
給你一個(gè)數(shù)組 nums 和一個(gè)值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間昭卓，你必須僅使用 O(1) 額外空間并原地修改輸入數(shù)組。
元素的順序可以改變瘟滨。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素葬凳。
示例 1:
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋?zhuān)汉瘮?shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素室奏。例如火焰，函數(shù)返回的新長(zhǎng)度為 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]胧沫，也會(huì)被視作正確答案昌简。
示例 2:
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3]
解釋?zhuān)汉瘮?shù)應(yīng)該返回新的長(zhǎng)度 5, 并且 nums 中的前五個(gè)元素為 0, 1, 3, 0, 4占业。注意這五個(gè)元素可為任意順序。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素纯赎。
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
思路：
本題是經(jīng)典的雙指針?biāo)惴}谦疾，對(duì)于一個(gè)數(shù)組來(lái)說(shuō)，刪除一個(gè)元素是比較復(fù)雜的犬金，每次刪除元素后念恍，若要保留原有的順序，則需要將后面的元素一個(gè)個(gè)先前“挪”一格位置晚顷，這樣操作的話峰伙，算法的時(shí)間復(fù)雜度是較高的。
所以就有了雙指針?lè)ǜ媚譃榭炻羔樂(lè)ㄒ约白笥抑羔樂(lè)ㄍィ軌驅(qū)崿F(xiàn)在一個(gè)for循環(huán)下完成兩個(gè)for循環(huán)的工作。
兩遍循環(huán)：
我們可以利用一種最樸素的方法栓袖，即暴力地使用兩遍for循環(huán)進(jìn)行求解匣摘，外層的for循環(huán)用于查找所要移除的元素，當(dāng)尋找到所要移除的元素值后裹刮，利用內(nèi)層的for循環(huán)音榜，將數(shù)組集體向前移動(dòng)一位。
//暴力解法
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 發(fā)現(xiàn)需要移除的元素
for (int j = i + 1; j < size; j++) { //將數(shù)組集體向前移動(dòng)一位
nums[j - 1] = nums[j];
}
i--; // 因?yàn)橄聵?biāo)i以后的數(shù)值都向前移動(dòng)了一位捧弃，所以i也向前移動(dòng)一位
size--; // 記錄此時(shí)的數(shù)組大小
}
}
return size;
}
快慢雙指針：
設(shè)置快慢雙指針囊咏，分別指向數(shù)組，完成各自任務(wù)塔橡。
快指針：不停止，勇往直前霜第，尋找目標(biāo)元素
慢指針：用于記錄更新新數(shù)組的下標(biāo)位置
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0; //初始化慢指針
for (int fast = 0; fast < nums.size(); fast++) { //快指針對(duì)整個(gè)數(shù)組進(jìn)行遍歷葛家，尋找目標(biāo)值
if (val != nums[fast]) { //若不為目標(biāo)值，更新慢指針泌类，并賦值給新數(shù)組
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
總的來(lái)說(shuō)快慢指針的概念還是挺容易理解的癞谒，使用起來(lái)也十分簡(jiǎn)介方便。
左右雙指針：
左右雙指針的思想與之前所提到的二分查找的思想比較相像刃榨，通過(guò)在數(shù)組的兩端設(shè)置左指針以及右指針弹砚，讓兩個(gè)指針在中間匯合。
在循環(huán)過(guò)程中枢希，當(dāng)左指針找到等于val的元素時(shí)桌吃，左指針會(huì)停下來(lái)。當(dāng)右指針找到不等于val的元素時(shí)苞轿，也會(huì)停下來(lái)茅诱，這時(shí)候逗物，右指針?biāo)赶虻牟坏扔趘al的元素會(huì)賦值給左指針?biāo)赶虻脑亍＝又螅灰笥抑羔樔晕磪R合翎卓，他們就會(huì)繼續(xù)朝著中間行走，重復(fù)剛剛的操作摆寄，直至兩者相遇失暴，結(jié)束對(duì)整個(gè)數(shù)組的遍歷。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0; //初始化左指針
int right = nums.size() - 1; //初始化右指針
while (left <= right) {
// 找左邊等于val的元素
while (left <= right && nums[left] != val) { //若不等于目標(biāo)值微饥，繼續(xù)遍歷
++left;
} //找到等于val值的元素時(shí)逗扒，結(jié)束循環(huán)
// 找右邊不等于val的元素
while (left <= right && nums[right] == val) {
--right;
} //找到不等于val值的元素時(shí)，結(jié)束循環(huán)
// 將右邊不等于val的元素覆蓋左邊等于val的元素
if (left < right) {
nums[left++] = nums[right--];
}
}
return left; // left指向最終數(shù)組末尾的下一個(gè)元素
}
}
題解參考：“代碼隨想錄”https://www.bilibili.com/video/BV12A4y1Z7LP
后續(xù)也會(huì)堅(jiān)持更新我的LeetCode刷題筆記畜号，歡迎大家關(guān)注我缴阎，一起學(xué)習(xí)。
如果這篇文章對(duì)你有幫助简软，或者你喜歡這篇題解蛮拔，可以給我點(diǎn)個(gè)贊哦。
往期回顧：
LeetCode367.有效的完全平方數(shù)
LeetCode69.x的平方根
LeetCode35.搜索插入位置
LeetCode704.二分查找
LeetCode34.在排序數(shù)組中尋找元素的第一個(gè)和最后一個(gè)位置
