移除元素

方法一：雙指針

題目要求在原數(shù)組的基礎(chǔ)進行元素的刪除，所以輸出的數(shù)組長度一定小于原數(shù)組的長度，因此可以使用雙指針，rigth 指針指向?qū)⒁幚淼脑?#xff0c;left 指針指向?qū)⒁x值的元素的位置。

• 如果 right 指針指向的元素不等于 val，那么它就一定是將要輸出的元素，將該元素賦值到 left 指針指向的位置，同時將 right 和 left 指針同時右移。
• 如果 right 指針指向的元素等于 val，那么它就一定不是要輸出的元素，此時 left 不動，right 右移。

最后 left 的值就是要輸出的數(shù)組的長度。

class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}
}

時間復(fù)雜度： O(n)
n 為數(shù)組的長度，最多只需要遍歷該數(shù)組兩遍

空間復(fù)雜度： O(1)
僅需要常數(shù)的空間保存若干變量

方法二：雙指針優(yōu)化

方法一中，我們的兩個指針都是從 0 開始的，實際上，我們可以一個指針從頭開始，一個指針從尾開始，這樣就最多僅需要遍歷一次數(shù)組就可以了。

class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right -- ;} else {left ++ ;}}return left;}
}

時間復(fù)雜度： O(n)
n 為數(shù)組的長度，最多只需要遍歷該數(shù)組一遍

空間復(fù)雜度： O(1)
僅需要常數(shù)的空間保存若干變量