双指针团灭删除有序数组中的重复项系列

公众号TanLiuYi00 · · 108 次点击 · · 开始浏览    

26. 删除有序数组中的重复项

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。

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

image
image

解题思路

由于题目已明确告知 不使用额外数组空间,必须在原地修改输入数组,因此不能采用诸如 哈希表 等通过开辟额外空间的方法去解决。又由于题目告知数组是 升序排列 的,因此可以通过 设置两个均指向数组第一个元素(从第零个元素开始算)的指针(下标),一个用于遍历整个数组,另一个用于比较遍历整个数组的指针指向的数组元素是否等于该指针指向的数组元素的后一个元素双指针法 去求解。

注意点

当数组长度 小于或者等于 1 时,即 数组为空或者数组只有一个元素 时,只需要直接返回数组长度即可。

举栗

以 nums = [0, 1, 1, 2, 3, 3] 为栗子,如下图示:

  1. 设置 快慢指针 f/s 并均指向数组的第一个元素。

    image

  2. nums[f] != nums[s - 1] = 0,将 nums[f] 赋值给 nums[s],并将 s 和 f 右移。
    image
  3. nums[f] == nums[s - 1] == 1,将 f 右移,s 保持不动。
    image
  4. nums[f] != nums[s - 1] == 1,继续将 nums[f] 赋值给 nums[s], s 和 f 右移。
    image
  5. nums[f] != nums[s - 1] == 2,将 nums[f] 赋值给 nums[s], s 和 f 右移。
    image
  6. nums[f] == nums[s - 1] == 3,继续将 f 右移,s 保持不动。
    image
  7. 快指针 f 遍历遍历完整个数组,直接返回 s 即可。

Show me the Code

c 语言

int removeDuplicates(int* nums, int numsSize){
    if(numsSize <= 1) {
        return numsSize;
    }

    int s = 1, f = 1;
    while(f < numsSize) {
        if(nums[f] != nums[s - 1]) {
            nums[s++] = nums[f];
        }
        f++;
    }     
    return s;
}

python3

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1: 
            return n
        f, s = 1, 1
        while f < n:
            if nums[f] != nums[s - 1]:
                nums[s] = nums[f]
                s += 1
            f += 1 
        return s

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

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 最多出现两次,返回删除后数组的新长度。

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

image

解题思路

本题与上题的区别仅在与 原地删除重复出现的元素后,使每个元素最多出现的次数,本题是 每个元素最多出现两次,上题是 每个元素最多出现一次,其它的 一毛一样,因此可以采用上一题的 双指针 方法,只不过本题是 比较 nums[s - 2](上上次放置的元素) 跟 nums[f](当前遍历的元素)的大小

Show me the Code

java

int removeDuplicates(int[] nums) {
    int n = nums.length;
    if(n <= 2) {
        return n;
    }

    int f = 2, s = 2;
    while (f < n) {
        if (nums[f] != nums[s - 2]) {
            nums[s++] = nums[f];
        }
        f++;
    }
    return s;
}

golang

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }

    s, f := 2, 2
    for f < n {
        if nums[f] != nums[s - 2] {
            nums[s] = nums[f]
            s++
        }
        f++
    }
    return s
}

往期精彩回顾

汉明距离(位运算,清晰图解)

更多精彩

关注公众号【程序员小熊】,后台回复【算法】或【python】,即可获取高清无码的经典算法或 python 电子书~

为了回馈读者,本公众号不定期会有送礼活动,敬请关注~


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:公众号TanLiuYi00

查看原文:双指针团灭删除有序数组中的重复项系列

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

108 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传