往期博客：

Leetcode1-两数之和详解

Leetcode2-两数相加代码详解

Leetcode20-有效的括号详解

Leetcode21-合并两个有序链表详解

Leetcode22-有效括号生成详解

Leetcode24-两两交换链表中的节点详解

目录

题目

示例

解析

双指针

代码

python代码

Java代码

题目

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

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

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

题目分析：

已知：数组 nums 和值 val

目的：原地移除所有数值等于 val 的元素

要求：返回数组新长度，使用 O(1) 额外空间

示例

示例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]，也会被视作正确答案。

示例2

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解析

双指针

既然题目要求必须仅使用 O(1) 额外空间，那么就不能引入其他额外的空间，必须在原始列表中进行修改，所以可以使用双指针法。

使用双指针法时，将左指针指向第一个元素，右指针指向最后一个元素，当左指针指向的元素不为2时向有移动，直到遇到后面第一个为2的元素时停止移动，将右指针向左移动，遇到前面第一个为2的元素停止移动，然后将左右指针处的元素积进行位置交换，依次进行，直到左右指针相遇停止。

让我们对具体情况进行分析，对于示例2：nums = [0,1,2,2,3,0,4,2], val = 2，首先设置左右指针

​

首先将左指针向右移，直到后面第一个为2的元素时停止

​

 然后将右指针向左移，直到前面第一个不为2的元素时停止

​

 交换左右指针处的元素

​

同理，将左指针继续向右移，右指针继续向左移

​

交换元素后继续移动

​

 当左右指针相遇时停止，此时需要注意，需要判断当前元素是否为2，如果为2，则新列表的长度就是左右指针当前所指元素的索引值，因为索引时从0开始，当前所指元素的索引值就是当前元素前面所有元素的个数，那如果当前元素不为2，则新列表的长度就是左右指针当前所指元素的索引值+1，具体情况看下图：

如果当前元素为2，则链表中不为2的元素有4个，而当前左右指针所指元素的索引值正好为4，所以直接返回当前元素的索引值

​

如果当前元素不为2，则链表中不为2的元素有5个，而当前左右指针所指元素的索引值为4，所以直接返回当前元素的索引值+1

​

代码

python代码

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        
        # 边界条件，当输入列表为空时，直接返回0
        if nums is None or len(nums) == 0:
            return 0
 
        # 设置左右指针
        left, right = 0, len(nums)-1
        
        while left < right:
            while (nums[left] != val and left < right):  # 移动左指针
                left += 1
            while (nums[right] == val and left < right):  # 移动右指针
                right -= 1
 
            nums[left], nums[right] = nums[right], nums[left]  # 交换两元素
        return left if nums[left] == val else left+1

Java代码

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