家好，很高興又見面了，我是姜茶的編程筆記，我們一起學習前端相關領域技術，共同進步，也歡迎大家關注、點贊、收藏、轉發，您的支持是我不斷創作的動力

鐵子們！從 2024/07/26 開始，我們進入算法專題篇的學習啦 。學習計劃如下：

1?? 每日一題;

2?? 學習順序是由易到難；

3?? 題目按照數據結構進行分類;

4?? 每個類型的題目預計安排 100 道題（簡單/中等/困難各 33 道）;

題目描述

27. 移除元素

給你一個數組 nums 和一個值 val，你需要原地移除所有數值等于 val 的元素。元素的順序可能發生改變。然后返回 nums 中與 val 不同的元素的數量。

假設 nums 中不等于 val 的元素數量為 k，要通過此題，您需要執行以下操作：

• 更改 nums 數組，使 nums 的前 k 個元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

示例 1：

輸入：nums=[3,2,2,3], val=3
輸出：2, nums=[2,2,,]
解釋：你的函數函數應該返回 k=2, 并且 nums 中的前兩個元素均為 2。你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。

示例 2：

輸入：nums=[0,1,2,2,3,0,4,2], val=2
輸出：5, nums=[0,1,4,0,3,,,_]
解釋：你的函數應該返回 k=5，并且 nums 中的前五個元素為 0, 1, 4, 0, 3。注意這五個元素可以任意順序返回。你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。

提示：

• 0 <=nums.length <=100
• 0 <=nums[i] <=50
• 0 <=val <=100

分析/求解

解決這個問題的關鍵在于我們要在原地操作數組，不能使用額外的空間來存儲新數組，同時要保證與 val 不同的元素在數組的前 k 個位置。以下是詳細的解釋和多種解決方法：

方法一：雙指針法（快慢指針）

雙指針法使用兩個指針，一個用于遍歷整個數組，另一個用于標記新數組的末尾。遍歷過程中，如果遇到與 val 不同的元素，就將這個元素放到新數組的末尾。

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只需要遍歷該序列至多兩次
• 空間復雜度：O(1)，我們只使用了常數級別的額外空間。

function removeElement(nums, val) {
    let i=0;
    for (let j=0; j < nums.length; j++) {
        if (nums[j] !==val) {
            nums[i]=nums[j];
            i++;
        }
    }
    return i;
}

方法二：雙指針法（交換法）

這種方法也是使用雙指針，但不同的是，當我們找到需要移除的元素時，將其與數組的最后一個元素交換，并減少數組的長度。這樣做的好處是可以減少復制操作，但數組元素的順序會被改變。

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只遍歷了一次數組。
• 空間復雜度：O(1)，我們只使用了常數級別的額外空間。

function removeElement(nums, val) {
    let i=0;
    let n=nums.length;
    while (i < n) {
        if (nums[i]===val) {
            nums[i]=nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    return n;
}

總結

對于像「移除特定元素」或「相同元素最多保留 k 位元素」這樣的問題，應該利用題目給定的要求分析出具體的「保留邏輯部分」，將「保留邏輯部分」應用到我們的遍歷到的每一個位置即可。

附件：

最后

如果有任何問題或建議，歡迎在評論區留言交流！祝你編程愉快！

道題的難點在于要求：不要使用額外的數組空間，必須僅使用 O(1) 額外空間并 原地 修改輸入數組。

這是一道很典型的雙指針題型，我們可以使用快慢指針來解決。

快慢指針

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement=function(nums, val) {
    let i=0;
    for (let j=0; j < nums.length; j ++) {
        if (nums[j] !==val) {
            nums[i++]=nums[j];
        }
    }
    return i;
};

由于題目中說明，可以改變順序，因此，我們可以用首尾指針交換元素位置來進行優化。

首尾指針