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

快慢指针法?

19 人参与  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://zhangshiyu.com/post/51674.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • 京圈佛子破戒后,我改嫁京圈纨绔(沈墨渊,白晶晶)
  • 前世被闺蜜害死,重生后我让她从太子妃变疯女苏婉儿,清歌完本_前世被闺蜜害死,重生后我让她从太子妃变疯女(苏婉儿,清歌)
  • 全书浏览七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)_七零军嫂太彪悍,带三宝上军区离婚(沈清落,陈桂花,陆有为)全书结局
  • 今天也没变成昨天(周扬陈默)全书免费_(周扬陈默)今天也没变成昨天后续(周扬陈默)
  • 重生后,秦总非要父以子贵(许沐晴,秦越泽)全书浏览_重生后,秦总非要父以子贵全书浏览
  • 他嫌弃我喝两块钱豆浆上不了台面,我结婚后他又哭又闹全书万照,白青青在线
  • 昭然若梦前尘烬列表_昭然若梦前尘烬(温昭然方池雲)
  • 导师借我股票账号,我倒欠五十万(孟潇潇,宁薇)_导师借我股票账号,我倒欠五十万孟潇潇,宁薇
  • 拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾(周钰泽,蒋清清,思源)全书浏览_拒绝把外卖券给舍友,竹马送我到迪拜捡垃圾全书浏览
  • 我的人生,你已出局(程森凌古楚文)_我的人生,你已出局程森凌古楚文
  • 穿书成病娇女配,睁眼就签下离婚协议书(朱楼)_穿书成病娇女配,睁眼就签下离婚协议书
  • 老婆逼我给白月光捐肾,我死后她悔疯了(宋逸晨沈墨白)全书浏览_老婆逼我给白月光捐肾,我死后她悔疯了全书浏览

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

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