移除元素

Leetcode算法练习第二十七题：移除元素

问题描述

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

解法一

使用双指针分别指向数组的开始与结尾，然后每找到一个与头指针所指位置元素相同的值，则在尾指针位置找一个不同的值进行交换，然后头指针往后移，尾指针往前移动直到二者相交。

解法二

同样使用双指针，不过两个指针都从头开始遍历，只是一个指针作为遍历的工作指针，而另一个用来记录新数组的尾元素位置，这样，每当工作指针找到一个跟欲删除元素不同的值就把新数组头元素与工作指针元素交换，然后二者分别后移直至结束。

复杂度

需要遍历数组，时间复杂度为O(n)；只需要空间复杂度借助两个指针元素，空间复杂度为O(1)。

Python 解法一

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums)==0:
            return 0

        r=len(nums)-1
        h=0
        while h<r:
            if nums[h]==val:
                if nums[r]==val:
                    r-=1
                else:
                    nums[h]=nums[r]
                    h+=1
                    r-=1
            else:
                h+=1
        b= h if h<r else r
        return b+1 if nums[b]!=val else b

Python解法二

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        pointer = 0
        for i in range(len(nums)):
            if nums[i] == val:
                continue
            nums[pointer] = nums[i]
            pointer += 1
        return pointer

C++解法二

static const auto io_sync_off=[](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int p=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==val)
                continue;
            nums[p++]=nums[i];
        }
        return p;
    }
};