【JS每日一算法】21.删除有序数组中的重复项(双指针)

给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致

由于在某些语言中不能改变数组的长度,所以必须将结果放在数组nums的第一部分。更规范地说,如果在删除重复项之后有k个元素,那么nums的前k个元素应该保存最终结果。

将最终结果插入nums的前k个位置后返回k

不要使用额外的空间,你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

更多JS版本题解点击链接关注该仓库👀

/**
 * @description: 双指针   TC:O(n)  SC:O(1)
 * @author: JunLiangWang
 * @param {*} nums 输入数组
 * @return {*}
 */
function doublePoint(nums){
    /**
     * 该方案利用双指针的方式,定义两个指针(low初值0,fast初值1),当两指针所指元素相同时,将fast指针继
     * 续向右移动直至遇到不同元素时(此时low与fast则会拉开一个区间,该区间的元素则为需要删除的相同的元
     * 素),将low指针向右移动一位,并将其赋值为fast指针所指元素(此时0到low指针所在区间的元素则是不重
     * 复的元素),当fast指针超出数组范围则终止循环,此时low位置+1则为去重后数组长度。
     */

    // 如果数组长度不大于1,无需去重直接返回即可
    if(nums.length<=1)return nums.length;
    // 定义两个指针
    let fastPoint=1,lowPoint=0;
    // 当fast指针超出数组范围则终止循环
    while(fastPoint<nums.length)
    {
        // 当两指针所指元素不同
        if(nums[lowPoint]!=nums[fastPoint])
        {
            // 将low指针向右移动一位
            lowPoint++;
            // 并将其赋值为fast指针所指元素
            nums[lowPoint]=nums[fastPoint];
        }
        // 继续移动fast指针
        fastPoint++;
    }
    return lowPoint+1;
}

原文链接:https://juejin.cn/post/7220075270664683580 作者:汪啊汪QAQ

(0)
上一篇 2023年4月10日 上午10:28
下一篇 2023年4月10日 上午10:41

相关推荐

发表回复

登录后才能评论