当前位置:首页 » 《随便一记》 » 正文

快慢指针法?

14 人参与  2023年01月20日 15:29  分类 : 《随便一记》  评论

点击全文阅读


力扣题目:27. 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

主要想解释一下代码随想录中的“快慢指针法”

本质其实就是将旧数组中的元素放到新数组中去而已,本质的代码如下

class Solution {public:    int removeElement(vector<int>& nums, int val) {        // 快慢指针法的本质如下,我觉得叫新旧指针法更好理解        // old_index遍历整个数组        vector<int> new_nums;   // 存放结果数组        for (int old_index = 0; old_index < nums.size(); old_index ++ )        {            if (nums[old_index] != val)             {                new_nums.push_back(nums[old_index]);            }        }        // 将新数组的值放回旧数组,这步不用在意,反正已经达不到题目要求的空间复杂的O(1)啦,就是AC一下,测试一下        for (int i = 0;  i < new_nums.size(); i ++ ) nums[i] = new_nums[i];        return new_nums.size();    }};

优化上述代码的空间

其实新数组(向量vector类型)new_nums没必要开,因为新数组的指针下标(好吧用了push_back,看不出指针下标了),那我再写个更好理解的代码如下:

class Solution {public:    int removeElement(vector<int>& nums, int val) {        // 快慢指针法的本质如下,我觉得叫新旧指针法更好理解        // old_index遍历整个数组        int new_nums[110];   // 存放结果数组        int new_index = 0;        for (int old_index = 0; old_index < nums.size(); old_index ++ )        {            if (nums[old_index] != val)             {                new_nums[new_index] = nums[old_index];                new_index ++ ;  // 新数组的指针            }        }        // 将新数组的值放回旧数组,这步不用在意,反正已经达不到题目要求的空间复杂的O(1)啦,就是AC一下,测试一下        for (int i = 0;  i < new_index; i ++ ) nums[i] = new_nums[i];        return new_index;    }};

这时候可以开始说了

注意看上一块代码,new_index指针指向的是结果数组,也就是去掉指定元素后的数组,old_index指针用于遍历旧数组,也就是原始数组。我们会发现,new_index指针移动起来不会比old_index指针快的,也就是new_index <= old_index, 为什么呢?因为old_index指针每查看一个旧数组的元素,就判断这个该不该放到新数组中去,也是查看一个判断一个,new_index最大也就是跟old_index一样大(此时情况:没有一个要删除的元素,旧数组当前已遍历到的元素全部丢到新数组中去)

综上,new_index既然不会比old_index大,那直接利用原始数组的空间即可,不用浪费空间开新数组了,旧数组已经被遍历过的位置是可以利用的啦。

代码如下:

class Solution {public:    int removeElement(vector<int>& nums, int val) {        // 快慢指针法的本质如下,我觉得叫新旧指针法更好理解        // old_index遍历整个数组        int new_index = 0;        for (int old_index = 0; old_index < nums.size(); old_index ++ )        {            if (nums[old_index] != val)             {                nums[new_index] = nums[old_index];                new_index ++ ;  // 新数组的指针            }        }        return new_index;    }};

附:我自己的双指针思路

我的双指针是丢头和尾,头那边的指针从头开始往后走,碰到要删除的,丢到末尾去就行(也就是和尾指针的元素交换位置),并将尾指针前移一位,相比快慢指针法(也就是上一块代码),缺点:改变了元素的的相对位置。

class Solution {public:    int removeElement(vector<int>& nums, int val) {        int len = nums.size();                // 与val相等的数与末尾数交换位置,并且长度减1        // 1 2 2 3 1  val = 1, 1丢到最后一位,并且长度减1        for (int i = 0; i < len; i ++ )        {            if (nums[i] == val)            {                swap(nums[i], nums[len - 1]);                len -- ;  // 长度                i -- ;    // 保持指针不动            }        }        return len;    }};

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/51674.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 热文推荐凤显,沐倾城附加(废后归来:嫡女狠角色)(凤显,沐倾城)最新章节列表
  • 24张化疗单无错版_任行洲舒卿小姐必读文_小说后续在线阅读_无删减免费完结_
  • 小说大结局小说沈黎小说已更新+特别篇(恶毒女配作上天冷面大佬跪地哄)纯净版
  • 装穷老婆为男大买YU7后悔疯了后续_沈如烟傅斯书傅先生精校文本_小说后续在线阅读_无删减免费完结_
  • 最新章节_笔趣阁(江东)江东小说(抗战之重整河山)在线畅读阅读
  • 恶毒女配作上天,冷面大佬跪地哄小说(沈黎)小说全集阅读连载中(恶毒女配作上天,冷面大佬跪地哄)_笔趣阁
  • 恶毒女配作上天冷面大佬跪地哄小说完结篇(沈黎)(恶毒女配作上天冷面大佬跪地哄)全书无套路阅读无广告小说大结局
  • 重生后我把妈妈换了,她却后悔了后续加长_妹妹林清母亲节精选作品_小说后续在线阅读_无删减免费完结_
  • 全网首发苏娆时砚清:+后续+番外(我曾经天真地以为,他也有片刻动心的牀)全本完整阅读无弹窗
  • 帮堂哥联系外科专家后,我上了手术台大反击_大伯母小凡明白后续更新+番外_小说后续在线阅读_无删减免费完结_
  • 兽世:穿成恶毒雌性后被反派大佬们强宠了小说(思雅)(兽世:穿成恶毒雌性后被反派大佬们强宠了)完整章节列表_笔趣阁
  • 迟暮不归推文_慕承川许依柔迟清夏爽文_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1