寫在前面

本專欄專注于分析與講解【面試經(jīng)典150】算法，兩到三天更新一篇文章，歡迎催更……

專欄內(nèi)容以分析題目為主，并附帶一些對(duì)于本題涉及到的數(shù)據(jù)結(jié)構(gòu)等內(nèi)容進(jìn)行回顧與總結(jié)，文章結(jié)構(gòu)大致如下，部分內(nèi)容會(huì)有增刪：

• Tag：介紹本題牽涉到的知識(shí)點(diǎn)、數(shù)據(jù)結(jié)構(gòu)；
• 題目來源：貼上題目的鏈接，方便大家查找題目并完成練習(xí)；
• 題目解讀：復(fù)述題目（確保自己真的理解題目意思），并強(qiáng)調(diào)一些題目重點(diǎn)信息；
• 解題思路：介紹一些解題思路，每種解題思路包括思路講解、實(shí)現(xiàn)代碼以及復(fù)雜度分析；
• 知識(shí)回憶：針對(duì)今天介紹的題目中的重點(diǎn)內(nèi)容、數(shù)據(jù)結(jié)構(gòu)進(jìn)行回顧總結(jié)。

Tag

【原地操作】【雙指針】【數(shù)組】

---

題目來源

面試經(jīng)典 150 題 —— 27. 移除元素

---

題目解讀

移除數(shù)組 nums 中的 val 值，要求原地操作，但是數(shù)組中的元素順序可以改變，最后輸出移除所有 val 后數(shù)組的長(zhǎng)度。

---

解題思路

方法一：原地操作

原地操作，那么我們就不能使用額外的數(shù)組來存放非 val 的元素從而實(shí)現(xiàn)移除操作，但是我們可以使用 “覆蓋” 的思想來模擬移除操作。

具體地，維護(hù)兩個(gè)指針 i 和 j，i 指針用來遍歷數(shù)組查找哪個(gè)位置上的元素等于 val，j 指向用來覆蓋 i 位置的元素。初始化 i = 0、j = nums.size() - 1，只要 nums[i] = val，我們就用 nums[j] 來覆蓋，使用了 nums[j] 之后，j 指針就要左移指向下一個(gè)將要使用的元素；只有 nums[i] != val 時(shí)，我們才會(huì)右移 i 指針，準(zhǔn)備處理下一個(gè)元素。

直到 i 指針超過 j 指針，表明可以被用來覆蓋的元素已經(jīng)沒有了，i 的值就是原數(shù)組中的非 val 的數(shù)，直接返回 i。

實(shí)現(xiàn)代碼

class Solution {
public:int removeElement(vector<int>& nums, int val) {int i = 0, j = nums.size() - 1;while (i <= j) {if (nums[i] == val) {nums[i] = nums[j--];}else ++i;}return i;}
};

復(fù)雜度分析

時(shí)間復(fù)雜度：$O(n)$，$n$ 為原數(shù)組 nums 的長(zhǎng)度。

空間復(fù)雜度：$O(1)$，僅使用了兩個(gè)指針變量，是原地操作。

---

寫在最后

如果文章內(nèi)容有任何錯(cuò)誤或者您對(duì)文章有任何疑問，歡迎私信博主或者在評(píng)論區(qū)指出 💬💬💬。

如果大家有更優(yōu)的時(shí)間、空間復(fù)雜度方法，歡迎評(píng)論區(qū)交流。

最后，感謝您的閱讀，如果感到有所收獲的話可以給博主點(diǎn)一個(gè) 👍 哦。