LeetCode27題：

github地址

有夢想的電信狗

前言

本文用C++實現LeetCode 第27題

---

題目描述

題目鏈接：https://leetcode.cn/problems/remove-element/

---

題目思路分析

目標分析：

1. 將數組中等于val的元素移除
2. 原地移除，意味著時間復雜度為O(n)，空間復雜度為O(1)
3. 返回nums中與val值不同的元素個數

思路：雙指針

• src：用于掃描元素，從待掃描元素的第一個開始，因此初始下標為0

• dst：指向數組中，最后一個位置正確的元素的下標，因此初始值為-1

• count：記錄賦值的次數，賦值的次數即為數組中與val值不同的元素個數，初始值為0

操作：

• nums[src] != val 時，說明：src位置的數無需被去掉，將其放在dst的下一個位置。
  • dst先++，指向可以放入下一個無需被刪除的元素的位置
  • 向nums[dst]賦值放入元素，之后src++
  • 計數器count++
• nums[src] == val 時，說明src位置的數需要被去掉，src++略過該元素。

代碼實現

• 時間復雜度：O(n)
• 空間復雜度：O(1)

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

---

算法代碼優化

• 時間復雜度：O(n)
• 空間復雜度：O(1)

通過觀察我們發現：

• dst和count自增的次數一樣，且初值分別為0和-1，因此count == dst + 1
• 且while循環內，if和else邏輯中，都執行了src++，因此if和else中的src++可以省略，直接將src在循環中++

 // 優化版
int removeElement(vector<int>& nums, int val) {int src = 0, dst = -1;while(src < nums.size()){if(nums[src] != val){++dst;nums[dst] = nums[src];}++src;}return dst + 1;
}

• 利用前置和后置++的特性最終優化，但不推薦這么寫，因為算法的可讀性下降了

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

---

以上就是本文的所有內容了，如果覺得文章對你有幫助，歡迎 點贊?收藏 支持！如有疑問或建議，請在評論區留言交流，我們一起進步

分享到此結束啦
一鍵三連，好運連連！

你的每一次互動，都是對作者最大的鼓勵！

---

征程尚未結束，讓我們在廣闊的世界里繼續前行！ 🚀