27. 移除元素

我不是女神ヾ 2023-10-13 15:53 53阅读 0赞

#### 27. 移除元素 ####

*  题干及输出示例
 *  为什么不把超过新数组长度的元素删掉
 *  解法
 *   *  暴力解法
     *  双指针法
     *   *  快慢指针法
         *  相向双指针法

## 题干及输出示例 ##

[力扣题目链接][Link 1]

给你一个数组 `nums` 和一个值 `val`，你需要 **原地**移除所有数值等于`val`的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 `O(1)` 额外空间并**原地**修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

输入：nums = \[3,2,2,3\], val = 3  
输出：2, nums = \[2,2\]  
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = \[2,2,3,3\] 或 nums = \[2,2,0,0\]，也会被视作正确答案。

## 为什么不把超过新数组长度的元素删掉 ##

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

## 解法 ##

### 暴力解法 ###

这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。时间复杂度是O(n^2)，空间复杂度是O(1)。

// 时间复杂度：O(n^2)
    // 空间复杂度：O(1)
    class Solution {
        
    public:
        int removeElement(vector<int>& nums, int val) {
        
            int size = nums.size();
            for (int i = 0; i < size; i++) {
        
                if (nums[i] == val) {
         // 发现需要移除的元素，就将数组集体向前移动一位
                    for (int j = i + 1; j < size; j++) {
        
                        nums[j - 1] = nums[j];
                    }
                    i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                    size--; // 此时数组的大小-1
                }
            }
            return size;
        }
    };

### 双指针法 ###

双指针法（快慢指针法）： **通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**

定义快慢指针  
快指针：**寻找新数组的元素** ，新数组就是不含有目标元素的数组。  
慢指针：指向更新 **新数组下标的位置**（也就是获取我们新数组中需要更新的位置）。

**双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。**

时间复杂度：O(n)  
空间复杂度：O(1)

#### 快慢指针法 ####

public int removeElement(int[] nums, int val){
        
            // 快慢指针
            int slowIndex = 0;
            for(int fastIndex = 0; fastIndex < nums.length; fastIndex++){
        
                if(nums[fastIndex] != val){
        
                    nums[slowIndex] = nums[fastIndex];
                    slowIndex++;
                }
            }
            return slowIndex;
        }

#### 相向双指针法 ####

public int removeElement(int[] nums, int val){
        
            int left = 0;
            int right = nums.length - 1;
            // 将right移到从右数第一个值不为val的位置
            while(right >= 0 && nums[right] == val) right--;
            while(left <= right){
        
                if(nums[left] == val) {
         //left位置的元素需要移除
                    //将right位置的元素移到left(覆盖)，right位置移除
                    nums[left] = nums[right];
                    right--;
                }
                left++;
                while(right >= 0 && nums[right] == val) right--;
            }
            return left;
        }

**参考资料**：[27. 移除元素][27.]

[Link 1]: https://leetcode.cn/problems/remove-element/
[27.]: https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF