leetcode80-删除排序数组中的重复项II

原题

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。

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

示例 1:

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解法

思想

leetcode26-删除排序数组中的重复项类似,这里也使用双指针,但是添加一个变量用于计数。

代码

解法一:使用额外变量count,慢指针始终停在每一组重复元素中的最多第二个元素上。

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int j = 0;
        int count = 1;
        while(j<nums.length-1){
            j++;
            // 如果遇到了新的字符,计数清零
            if(nums[j]!=nums[j-1]) count = 0;
            // 如果计数小于二,将后面那个指针指向的值赋给前面那个指针指向的值
            if(count<2){
                count++;
                nums[++i] = nums[j];
            }
        }
        return i+1;
    }
}

解法二:慢指针停留在要检查的元素上(可能要改成别的值)

func removeDuplicates(nums []int) int {
    i := 2
    j := 2
    if len(nums) < 2{
        return len(nums)
    }
    for j < len(nums) {
        if nums[i - 2] != nums[j]{
            nums[i] = nums[j]
            i ++
        }
        j ++
    }
    return i
}

用遍历代替快指针的另一种写法:

func removeDuplicates(nums []int) int {
    return process(nums, 2)
}

func process(nums []int, k int) int {
    slow := 0
    for _, v := range nums {
        if slow < k || nums[slow-k] != v {
            nums[slow] = v
            slow++
        }
    }
    return slow
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode80-%e5%88%a0%e9%99%a4%e6%8e%92%e5%ba%8f%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e9%87%8d%e5%a4%8d%e9%a1%b9ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月25日
下一篇 2020年5月26日

相关推荐

  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0150
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode279-完全平方数

    原题 给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出…

    2019年12月11日
    0150
  • leetcode739-每日温度

    原题 根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定一个列表 te…

    算法 2019年12月11日
    0130
  • 海量数据去重-由BitMap引出的布隆过滤器

    本文参考资源: 那些惊艳的算法们(一)——布隆过滤器_C/C++_xinzhongtianxia的博客-CSDN博客 详解布隆过滤器的原理、使用场景和注意事项 - 简书 概述 昨天…

    2020年2月28日
    01.3K0
  • leetcode85-最大矩形

    原题 给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [   ["1","0","1","0","0"…

    2020年1月24日
    0200
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode31-下一个排列

    原题 整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。 例如,arr = [1,2,3] ,以下这些都可以视作 arr 的排列:[1,2,3]、[1,3,2]、[3,1…

    算法 2022年4月13日
    02613
  • leetcode154-寻找旋转排序数组中的最小值II

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。…

    算法 2020年1月7日
    090
  • 程序员面试金典01.07-旋转矩阵

    原题(来源Leetcode) 给你一幅由 N × N 矩阵表示的图像,其中每个像素的大小为 4 字节。请你设计一种算法,将图像旋转 90 度。 不占用额外内存空间能否做到? 示例 …

    算法 2020年4月7日
    0410

发表回复

登录后才能评论