E

EdwardWong

V1

2022/09/15阅读:43主题:姹紫

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: 注意移除元素之后,要对sizei减一。

快慢指针

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

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

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

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        //使用双指针解题可以只使用一层循环解决问题
        int slow =0;
        if(nums.size()==0return 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

分类:

后端

标签:

数据结构与算法

作者介绍

E
EdwardWong
V1