題目：給定一個陣列 nums 和一個值 val ，你需要原地移除所有數值等于 val 的元素，回傳移除后陣列的新長度，不要使用額外的陣列空間，你必須在原地修改輸入陣列并在使用 O(1) 額外空間的條件下完成，OJ鏈接.
法一：暴力法
決議：
我們來決議一下這個題目的做題思路，他的含義就是讓我們洗掉掉陣列中的元素，然后將陣列后面的元素跟上來，最后回傳洗掉掉元素的陣列長度即可，比如陣列長度為 10，里面有2個目標值，我們最后回傳的長度為 8，但是回傳的 8 個元素，需要排在陣列的最前面，那么暴力解法的話則就需要兩個 for 回圈，一個用來找到洗掉，另一個用來更新陣列，
總體思路就是這樣的，后面的會不斷往前覆寫，暴力解法也是不超時的，實作也不算太簡單主要需要注意兩個地方，
（1）需要先定義變數len獲取陣列長度，因為后面我們的回傳的陣列長度是改變的，所以不可以用 nums.length 作為上界
（2）我們每找到一個需要洗掉的值的時候，需要i–，防止出現多個需要洗掉的值在一起的情況，然后漏刪，
題目代碼
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = nums.size();
for(int i = 0; i<len; i++)
{
if(nums[i] == val)
{
for(int j = i;j<len-1;j++)
{
nums[j] = nums[j+1];
}
i--;
len--;
}
}
return len;
}
};
法二：雙指標
快慢指標的做法只需要一個 for 回圈即可解決，時間復雜度為 O(n) ,總體思路就是有兩個指標，前面一個后面一個，前面的用于搜索需要洗掉的值，當遇到需要洗掉的值時，前指標直接跳過，后面的指標不動，當遇到正常值時，兩個指標都進行移動，并修改慢指標的值，最后只需輸出慢指標的索引即可，
// 時間復雜度：O(n)
// 空間復雜度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249861.html
標籤：其他