[27. Remove Element]
[(https://leetcode.cn/problems/remove-element/)
思路
- 陣列在記憶體中是連續的，根據此題要求不能洗掉，而是覆寫
暴力解法
-
此題暴力解法是兩層for回圈，一個回圈遍歷陣列元素 ，第二個回圈更新陣列
-
時間復雜度：O(n^2)
空間復雜度：O(1)
雙指標法
- 雙指標法：又叫快慢指標法， 一個快指標和慢指標在一個for回圈下完成兩個for回圈的作業
- 首先，我們需要定義雙指標的含義：
- 快指標：尋找新陣列（不含有val）的元素
- 慢指標：指向新陣列的下標
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if(nums.size() == 0) return 0;
int slowindex = 0, fastindex = 0; //定義快慢指標
for(; fastindex < nums.size(); ++fastindex) //因為快指標是尋找新元素，因此需限定快指標范圍
{
//若尋找的此新元素等于val，則跳過
if(nums[fastindex] != val)
{
nums[slowindex++] = nums[fastindex];
}
}
return slowindex; //因為慢指標是指向新陣列的下標，因此只需回傳慢指標索引值
}
};
-
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513062.html
標籤：其他