当前位置: 首页 > article >正文

移除元素(双指针)

给你一个数组 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。

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

暴力解法

这个题目暴力的解法就是两层for循环,一个for循环遍历数组元素 ,第二个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; i++) {
            if (nums[i] == val) { // 发现需要移除的元素,就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

双指针法

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

  • 快指针:寻找新数组的元素 ,新数组就是不含有目标元素的数组
  • 慢指针:指向更新 新数组下标的位置

很多同学这道题目做的很懵,就是不理解 快慢指针究竟都是什么含义,所以一定要明确含义,后面的思路就更容易理解了。

双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。

代码:

// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

注意这些实现方法并没有改变元素的相对位置!

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)
/**
* 相向双指针方法,基于元素顺序可以改变的题目描述改变了元素相对位置,确保了移动最少元素
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int leftIndex = 0;
        int rightIndex = nums.size() - 1;
        while (leftIndex <= rightIndex) {
            // 找左边等于val的元素
            while (leftIndex <= rightIndex && nums[leftIndex] != val){
                ++leftIndex;
            }
            // 找右边不等于val的元素
            while (leftIndex <= rightIndex && nums[rightIndex] == val) {
                -- rightIndex;
            }
            // 将右边不等于val的元素覆盖左边等于val的元素
            if (leftIndex < rightIndex) {
                nums[leftIndex++] = nums[rightIndex--];
            }
        }
        return leftIndex;   // leftIndex一定指向了最终数组末尾的下一个元素
    }
};

http://www.kler.cn/a/2152.html

相关文章:

  • 【 C语言练习(4)—可自己设置游戏规则的猜数字游戏】
  • 【ROS2】深度相机ROS2包的使用
  • 从0开始边做边学,用vue和python做一个博客,非规范化项目,怎么简单怎么弄,跑的起来有啥毛病解决啥毛病(三)
  • 一次“okhttp访问间隔60秒,提示unexpected end of stream“的问题排查过程
  • 企业邮箱为什么不能经常群发邮件?
  • 防止浏览器控制台修改网页数据与函数的方法
  • 《剑指Offer》笔记题解思路技巧优化——精心编写(1)
  • “你要多弄弄算法”
  • 南京邮电大学数据库第三次课后作业
  • 什么是推挽输出,开漏输出?
  • 【嵌入式硬件芯片开发笔记】HART协议调制解调芯片AD5700配置流程
  • Qt优秀开源项目之十七:QtPromise
  • PostgreSQL学习总结(12)—— PostgreSQL 内置函数汇总
  • 第十七天 JavaScript、Vue详细总结
  • 队列实现及leetcode相关OJ题
  • Redis 如何实现库存扣减操作和防止被超卖?
  • 【业务安全-02】业务逻辑漏洞之越权操作
  • 测试老鸟都在用的接口抓包常用工具以及接口测试工具都有哪些?
  • 【C++】二叉搜索树
  • WebService简单入门
  • python+django+vue全家桶鲜花商城售卖系统
  • 机器学习——无监督学习
  • 基于java下的Springboot框架实现幼儿园管理系统
  • 【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(6)
  • 使用GPT-4生成QT代码
  • 使用 Python 从点云生成 3D 网格