您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

LeetCode琅琊榜第十一层-删除有序数组中的重复项 II(快慢双指针)

LeetCode.80删除有序数组中的重复项 II

难度:中等

博主空间与往期力扣

题目链接 


目录

作者原始思路

计数法

思想和代码简述

问题

反省

官方解法-快慢双指针

快慢双指针的思想概念

代码实现

代码分析

结论


作者原始思路

计数法

class Solution {
    public int removeDuplicates(int[] nums) {
        var isRead = new int[20000]; // 计数数组
        var count = 0; // 统计替换个数
        for (int i = 0; i < nums.length; i++) {
            isRead[nums[i]+10000]++;
            if(isRead[nums[i]+10000] >= 3) {
                nums[i] = Integer.MAX_VALUE;
                count++;
            }
        }
        Arrays.sort(nums);
        return nums.length - count;
    }
}

思想和代码简述

  • 创建一个计数数组,用于记录每一个元素出现的次数,当出现的次数大于二时,我们就将其进行替换
    • 1.由题目可知,数组里面的元素取值范围是[-10000,10000],有小于0的数字,由于数组的下标从0开始,所以赋值上去的时候都要加上10000,保证都大于0
    • 2.如果发现出现次数大于2的元素,我们就要把他替换成Integer.MAX_VALUE,并记录更改的次数
    • 3.最后再对数组进行排序
    • 4.返回nums.length - count个长度,有效去除了更改后的元素,得到目标数组
    • 5.如果不会统计思想,详情请看<<有效数独>>

问题

执行的太慢了,我不满意

反省

  • 一开始我也想到了快慢双指针的算法,奈何不会,写不出来,无奈之下选择了计数法,计数法时间复杂度虽然是O(N),还挺好,但是,用到了额外的空间,代码效率大大降低,所以,终究还是得要快慢双指针出马

官方解法-快慢双指针

快慢双指针的思想概念

  • 1.设快指针为fast,慢指针为slow
  • 2.初始化
    • 2.1fast初始化在最开始的未遍历的元素上
    • 2.2slow初始化在最后一个被处理的元素的后一个位置上
    • 2.3即fast和slow的初始化是一致的
  • 3.作用
    • 3.1fast的作用主要是遍历未处理的元素
    • 3.2slow的作用主要是处理元素

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n <= 2) {
            return n;
        }
        int slow = 2, fast = 2;
        while (fast < n) {
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

代码分析

  • 1.先校验一下,如果数组长度小于等于2,说明一定没有元素超过两个,直接返回即可
  • 2.slow和fast的都初始化为2
    • 原因:对于下标为0和1的元素,他们无非只有两种情况,即相等或不相等,如果相等,该元素出现次数只为2,符合题意,如果不相等,没有违反题意
    • 所以,前面两个元素默认为处理过的元素,所以下标从2开始!
  • 3,循环详解
    • 3.1fast < n 原因:由于fast指针指向未处理元素,元素下标最大为n - 1,所以fast < n
    • 3.2nums[slow-2] 原因:对于后面两个位置即slow - 1和slow - 2位置,他们无非只有两种结果,即相等或不等,满足条件
    • 为什么不用slow - 1 去判断 或者 slow去判断呢?
      • 1.用fast和slow-2的元素去比较,无非只有两种结果,即相等或不相等
        • 当相等的时候,说明有三个元素一致
        • 当不相等时,有且最多有两个元素一致
        • 符合题意
        • 倘若fast指向的元素与slow - 2指向的元素相等时,说明当前这个位置是需要被处理的,但不能liji,所以slow不++,fast++
        • 倘若fast指向的元素与slow - 2指向的元素不相等时,说明这个位置这个位置不需要被处理,slow++
        • 但是,两种情况一结合,我们发现一个需要被处理,最终没有被处理,而第二种情况slow++了,所以我们要在其++前处理,即nums[slow] = nums[fast]
        • nums[slow] = nums[fast]一旦执行,说明slow指向的一定是多余的元素,用后面fast的元素覆盖
  • 注意:由于覆盖,后面的元素可能也会出现超过三个的可能性,经过覆盖会得到正确的结果

结论

        快慢双指针,思考起来还是有一些难度的,所以要多练呀!包括博主也是,你给我一道创新的快慢双指针,我也不一定能写的出来,所以,练才是王道

        我来总结一下几点:

        1.快慢双指针元素的思想定义

                2.代码实现与分析


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进