27. 移除元素【 力扣(LeetCode) 】

一、题目描述

  给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

  假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

1. 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
2. 返回 k。

二、测试用例

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

二、解题思路

1. 基本思路：题目允许元素顺序发生改变，那么，可以使用不需要删除的元素来填充需要删除的元素，来避免移动大量元素。
2. 具体思路：
   • 双指针：维护两个指针 i 和 k ，初始化为 0 。指针 i 用于遍历数组，寻找不需要删除的元素，指针 k 用处存放不需要删除的元素，每次指针 i 找到不需要删除的元素，便赋值给指针 k ，直到遍历结束。【最坏情况，遍历两次序列，指针 i 一次，指针 k 一次】
   • 快排思想：借助快排思想，将序列划分为左右两个部分，左边存放不需要删除的元素，右边存放需要的删除的元素。也是维护两个指针 i 和 k ，不过指针 i 初始化为 0 ，用于寻找需要删除的元素；指针 k 初始化为序列最后一个元素的位置，用于寻找不需要删除的元素；一旦两个指针都找到对应元素，便将指针 k 所指的元素赋值给指针 i ，然后继续寻找，直到两个指针相遇。【只遍历一遍序列】

三、参考代码

3.1 双指针

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

最好情况：遍历一遍序列，即删除全部元素，只有指针 i 移动。
最坏情况：遍历两遍序列，即不需要删除元素，指针 i 和 k 都需要移动

int removeElement(vector<int>& nums, int val) {
    int n=nums.size();
    int k=0;
    for(int i=0;i<n;i++){
        if(nums[i]!=val){
            nums[k++]=nums[i];
        }
    }
    return k;
}

3.2 快排思想

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

最坏和最好情况都是遍历一遍序列。

int removeElement(vector<int>& nums, int val) {
    int k=nums.size()-1;
    int i=0;
    while(i<=k){
        while(i<=k&&nums[i]!=val) i++;
        while(i<=k&&nums[k]==val) k--;
        if(i>k) break;
        nums[i]=nums[k];
        k--;
    }
    return k+1;
}