【LeetCode_27】移除元素

LeetCode27题：

github地址

有梦想的电信狗

前言

本文用C++实现LeetCode 第27题

题目描述

题目链接：https://leetcode.cn/problems/remove-element/

题目思路分析

目标分析：

1. 将数组中等于val的元素移除
2. 原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1)
3. 返回nums中与val值不同的元素个数

思路：双指针

• src：用于扫描元素，从待扫描元素的第一个开始，因此初始下标为0

• dst：指向数组中，最后一个位置正确的元素的下标，因此初始值为-1

• count：记录赋值的次数，赋值的次数即为数组中与val值不同的元素个数，初始值为0

操作：

• nums[src] != val 时，说明：src位置的数无需被去掉，将其放在dst的下一个位置。
  • dst先++，指向可以放入下一个无需被删除的元素的位置
  • 向nums[dst]赋值放入元素，之后src++
  • 计数器count++
• nums[src] == val 时，说明src位置的数需要被去掉，src++略过该元素。

代码实现

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

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
         int src = 0, dst = -1;
         int count = 0;
         while(src < nums.size()){
             if(nums[src] != val){
                 ++dst;
                 nums[dst] = nums[src];
                 src++;
                 ++count;
             }
             else{
                 ++src;
             }
         }
         return count;
    }
};

算法代码优化

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

通过观察我们发现：

• dst和count自增的次数一样，且初值分别为0和-1，因此count == dst + 1
• 且while循环内，if和else逻辑中，都执行了src++，因此if和else中的src++可以省略，直接将src在循环中++

 // 优化版
int removeElement(vector<int>& nums, int val) {
    int src = 0, dst = -1;
    while(src < nums.size()){
        if(nums[src] != val){
            ++dst;
            nums[dst] = nums[src];
        }
        ++src;
    }
    return dst + 1;
}

• 利用前置和后置++的特性最终优化，但不推荐这么写，因为算法的可读性下降了

class Solution {
public:
   int removeElement(vector<int>& nums, int val) {
        int src = 0, dst = -1;
        while(src < nums.size()){
            if(nums[src] != val)
                nums[++dst] = nums[src++];
            else
                ++src;
        }
        return dst + 1;
    }
};

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！

你的每一次互动，都是对作者最大的鼓励！

---

征程尚未结束，让我们在广阔的世界里继续前行！ 🚀