【C/C++练习】经典的快慢指针问题---移除元素

这篇具有很好参考价值的文章主要介绍了【C/C++练习】经典的快慢指针问题---移除元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C/C++练习】经典的快慢指针问题---移除元素

📖题目描述

【C/C++练习】经典的快慢指针问题---移除元素
题目出处:移除元素

🔖示例

【C/C++练习】经典的快慢指针问题---移除元素

📖题解

 对于本题我将按照由易到难的顺序为大家分享三种解题思路,并逐一分析它们的优劣,以及注意事项。

🔖思路一:暴力求解

 我想暴力求解应该是第一次接触到此题的小伙伴们最先想出来的办法吧。这道题目暴力求解就是去遍历数组,当遇到数组元素等于val的时候,将后面的所有元素往前挪动一位,把val覆盖掉以实现移除的效果。具体过程如下动图所演示:
【C/C++练习】经典的快慢指针问题---移除元素
代码实现:

int removeElement(int* nums, int numsSize, int val)
{
    int i = 0;
    int len = numsSize;
    while(i < len)
    //循环控制变量用len,因为如果有重复,就会往前覆盖
    {
        if (nums[i] == val)
        {
            int j = 0;
            for (j = i; j < len; j++)
            //把后面的往前覆盖
            {
                if (j != numsSize - 1)
                {
                    nums[j] = nums[j + 1];
                }
            }
            len--;
            //找到一个之后跳出循环,继续从下标为0的数字开始检查
            }
        else
        {
            i++;
        }
    }
    return len;
}

 需要注意:i是用来遍历整个数组的,当nums[i] == val的时候停下来,把i后面的所有数据往前挪动一位,且数组的有效长度len减一。挪动完后i的值不变,因为此时i位置上的元素是它后一位经过挪动覆盖过来的,我们并不知道他是否等于val,因此需要继续判断num[i]是否等于val,如果不等于再让i++继续去遍历后面的元素,直到i等于数组的有效长度,此时说明已经遍历结束。

复杂度分析:
 时间复杂度要讨论最坏的情况,对于本题最坏情况就是数组中所有的元素都等于val,假设数组一共有 N N N个元素,那么将第一个元素移除需要把后面的 N − 1 N-1 N1个元素全部往前挪动一位,也就是挪动 N − 1 N-1 N1次,由于数组元素全是val所以经过挪动后第一个元素任然是val,但此时数组的有效元素个数已经变成了 N − 1 N-1 N1,所以此时需要挪动 N − 2 N-2 N2…以此类推总的挪动次数就是一个等差数列求和,因此时间复杂度就是 O ( N 2 ) O(N^2) O(N2)

🔖思路二:空间换时间

 如果对空间复杂度没有要求的情况下,我们可以创建一个新数组,然后去遍历原数组,如果num[i]不等于val就把他拷贝到新数组,如果等于那就跳过并且有效数据个数减一,直到遍历结束,然后把新开数组的内容拷贝回原数组。具体过程如下动图所示:
【C/C++练习】经典的快慢指针问题---移除元素
代码实现:

int removeElement(int* nums, int numsSize, int val)
{
    int len = 0;
    int* tmp = (int*)malloc(sizeof(int)*numsSize);
    for(int i = 0; i < numsSize; i++)
    {
        if(nums[i] != val)
        {
            tmp[len++] = nums[i]; 
        }
    }
    memcpy(nums, tmp, sizeof(int)*len);
    return len;
}

复杂度分析:
 时间复杂度方面,这种方案只遍历了一遍数组,因此它的时间复杂度是 O ( N ) O(N) O(N),在空间复杂度方面,由于开辟了一个新数组,所以空间复杂度是 O ( N ) O(N) O(N)

🔖思路三:双指针

 这种思路的具体过程是:同时维护两个指针,分别记作pripos,让他俩从第一个元素开始同时往后走,当pos指向的元素不等于val的时候,把其赋值给pri所指向的位置,然后两个指针继续往后走,如果pos指向的元素等于val,那么pri停下来,pos跳过这个元素继续往后走,直到pos指向的元素不等于val,把它赋值给pri指向的位置,然后两个指针继续同时往后走,直到pos指针来到数组的结尾。具体过程如下动图所示:
【C/C++练习】经典的快慢指针问题---移除元素
代码实现:

int removeElement(int* nums, int numsSize, int val)
{
    int pri = 0, pos = 0;
    while(pos < numsSize)
    {
        if(nums[pos] != val)
        {
            nums[pri] = nums[pos];
            pri++;
        }
        pos++;
    }
    return pri;
}

复杂度分析:
 在时间复杂度方面,这种方法只遍历了一遍数组,所以时间复杂度是 O ( N ) O(N) O(N),在空间复杂度方面,由于没有额外申请空间所以空间复杂度是 O ( 1 ) O(1) O(1)。对于这道题思路三无疑是最好的方法,这种快慢指针的思想大家要多多去体会。

📖题目描述

【C/C++练习】经典的快慢指针问题---移除元素
【C/C++练习】经典的快慢指针问题---移除元素

题目出处:删除有序数组中的重复项

📖题解

 有了上面的分析基础,我们应该很容易猜到这道题也可以使用双指针的方法来做,但是这个题的双指针与上面的又有所不同。这道题要让pri指针从第一个元素开始,pos指针从第二个元素开始,因为相同的元素只需要保存一个,如果pos指向的元素与pri指向的元素相等就让pos往后走而pri不动,直到pos指向的元素不等于pri指向的元素,此时先让pri往后走一步,然后把pos指向的元素赋值给pri指向的元素,具体过程如下动图所示:
【C/C++练习】经典的快慢指针问题---移除元素
代码实现:

int removeDuplicates(int* nums, int numsSize)
{
    int pri = 0;
    int pos = pri + 1;
    while(pos < numsSize)
    {
        if(nums[pos] != nums[pri])
        {
            pri++;
            nums[pri] = nums[pos];
        }
        pos++;
    }
    return ++pri;
}

 今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,您的支持就是春人前进的动力!

【C/C++练习】经典的快慢指针问题---移除元素文章来源地址https://www.toymoban.com/news/detail-503074.html

到了这里,关于【C/C++练习】经典的快慢指针问题---移除元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【面试经典150题】移除元素·JavaScript版

    题目来源 给你一个数组 nums 和一个值 val ,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组 。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 0 = nums

    2024年02月11日
    浏览(39)
  • 单链表相关经典算法OJ题:移除链表元素

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 题目:移除链表元素 解法一: 解法一的代码实现: 解法二: 解法二代码的实现: 总结 世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力学习编程的你!一个爱学编程的人。各

    2024年02月04日
    浏览(48)
  • 【LeetCode题目详解】(一些双指针的题目)27. 移除元素

    给你一个数组 nums   和一个值 val ,你需要 原地 移除所有数值等于  val   的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组 。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什

    2024年01月22日
    浏览(42)
  • 算法:移除数组中的val的所有元素---双指针[2]

    文章来源: https://blog.csdn.net/weixin_45630258/article/details/132689237 欢迎各位大佬指点、三连 1、题目: 给你一个数组 nums和一个值 val,你需要 原地移除 所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地修改 输入

    2024年02月09日
    浏览(45)
  • 数据结构c语言版:顺序表oj题练习(原地移除元素、合并两个有序数组)

    在单数组里面历遍找val,如果是val,就删除。不是就跳过。 时间复杂度O(n^2),最坏情况每个都是val。相当于一个等差数列。 比如 下标0开始找,0不是,不动数组 下标1,1不是,不动数组 下标2,2是,删除元素,变成【0,1,2,3,0,4,2】 下标2,2是,删除元素,变成【0,

    2024年01月23日
    浏览(67)
  • C语言移除元素问题解决方法详解

    本文详细介绍了解决移除元素问题的三种方法:暴力求解、空间换时间和双指针方法,帮助读者更好地理解和解决类似问题。

    2023年04月24日
    浏览(37)
  • 快慢指针、双指针

    快慢指针,双指针不是数据结构,而是操作方法,使用的目的是降低时间复杂度,使得原本需要两个for循环的,只用一个就能实现 快慢指针 141. 环形链表 - 力扣(LeetCode) 27. 移除元素 - 力扣(LeetCode) 双指针  比如反转字符串,一个指针在头,一个在尾,元素交换后,两个

    2024年02月03日
    浏览(35)
  • 【LeetCode】 双指针,快慢指针解题

    1.删除有序数组中的重复项 2.移除元素

    2024年02月11日
    浏览(59)
  • 【算法|数组】快慢指针

    给你一个数组 nums 和一个值 val ,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组 。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 首先有一个点我们

    2024年02月13日
    浏览(44)
  • 快慢指针该如何操作?本文带你认识快慢指针常见的三种用法及在链表中的实战

    很多同学都听过 快慢指针 这个名词,认为它不就是定义两个引用(指针)一前一后吗?是的,它的奥秘很深,它的作用究竟有哪些?究竟可以用来做哪些题目?下面我将一一带你了解和应用 下面的本节的大概内容,有疑惑的点,欢迎小伙伴们留言 目录 1.简述快慢指针 2.快慢

    2024年02月04日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包