LeetCode 27 移除元素

LeetCode 27 移除元素

题目示例：

给你一个数组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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素

解题思路

暴力算法

本题可以使用暴力算法，使用双层for循环,时间复杂度是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-1;i++){
            if(nums[i]==val){
                for(int j=i+1;j<=size-1;j++){
                    nums[j-1]=nums[j];
                } 
                i--;   //此时需要注意要将循环变量i的值减少1，因为整体向前移动了一位，后面在执行完if操作后会进行i++的操作
                size--;  //也要注意移除了一个元素后，这个size变量需要减少1，否则会出现数组越界的情况
            }
        }
        return size; 
    }
};

Note： 注意移除元素之后，要对size和i减一。

快慢指针

使用双指针从而可以写一层for循环，其中快指针指向数组的元素值，慢指针记录更新数组的下标位置。

• 如果快指针指向的元素不等于val,它一定是输出数组的一个元素，我们就将快指针指向的元素复制到慢指针的位置，然后将快慢指针同时右移；

• 如果快指针指向的元素等于val，需要移除此元素，并将慢指针的位置保持不动。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //使用双指针解题可以只使用一层循环解决问题
        int slow =0;
        if(nums.size()==0) return 0;
        for(int fast=0;fast<=nums.size()-1;fast++){   // i是快指针
            if(nums[fast]!=val){   //如果快指针指向的数组元素等于要移除的目标值，那么快指针继续向后走，慢指针维持不动，如果指向的数组元素不等于要移除的目标值，那么快慢指针都向前移动
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
};

优化双指针

对于第二种方法，快慢指针都要循环遍历数组一次，为了减少循环遍历的次数，可以将左指针指向数组的左边，右指针指向数组的右边。

• 如果左指针指向的元素等于val，那么将右指针指向的数组元素赋值给左指针指向的数组元素，然后向左移右指针。 需要注意的是，此时左指针刚刚被赋予的新元素仍然可能为val，还要进行判断， 直至当左指针的元素值不等于val，左指针向右移。

C++ 版本

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //使用双指针的优化，慢指针指向数组前半段，快指针指向数组后半段
        int left=0;
        int right=nums.size();
        while(left<right){   //用for循环不好确定终止循环条件，此时使用while循环非常方便，当慢指针向右走，快指针向左走，两个指针相等的时候，就终止循环
            if(nums[left]==val){
                nums[left]=nums[right-1];
                right--;
            }else{
            left++;
            }
        }
        return left;
    }
};

Python版本

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left=0
        right=len(nums)-1
        ## 需要判断nums数组是否为空，如果为空的话直接返回0
        if (right==-1):
            return 0

        while(left<=right):
            if(nums[left]==val):  ## 如果左指针指向的元素等于val，那么把右指针指向的元素复制到左指针的位置
                nums[left]=nums[right]
                right-=1
                left-=1
            left+=1

        return left