1. 首页
  2. Leetcode经典148题

leetCode-80-Remove-Duplicates-from-Sorted-ArrayII

题目描述(中等难度)

leetCode-80-Remove-Duplicates-from-Sorted-ArrayII

“>26 题的思想,慢指针指向满足条件的数字的末尾,快指针遍历原数组。并且用一个变量记录当前末尾数字出现了几次,防止超过两次。

public int removeDuplicates(int[] nums) {
    int slow = 0;
    int fast = 1;
    int count = 1;
    int max = 2;
    for (; fast < nums.length; fast++) {
        //当前遍历的数字和慢指针末尾数字不同,就加到慢指针的末尾
        if (nums[fast] != nums[slow]) { 
            slow++;
            nums[slow] = nums[fast];
            count = 1; //当前数字置为 1 个
        //和末尾数字相同,考虑当前数字的个数,小于 2 的话,就加到慢指针的末尾
        } else {
            if (count < max) {
                slow++;
                nums[slow] = nums[fast];
                count++; //当前数字加 1
            }
        }
    }
    return slow + 1;
}

时间复杂度:O(n)。

空间复杂度:O(1)。

解法二

参考//相等的情况 1 1 1 1 1 2 2 3 ^ ^ s f //不相等的情况 1 1 1 1 1 2 2 3 ^ ^ s f

public int removeDuplicates2(int[] nums) {
    int slow = 1;
    int fast = 2;
    int max = 2;
    for (; fast < nums.length; fast++) {
        //不相等的话就添加
        if (nums[fast] != nums[slow - max + 1]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

时间复杂度:O(n)。

空间复杂度:O(1)。

快慢指针是个好东西,解法二直接利用有序,和倒数第 n 个比,从而保证末尾的数字不超过 n 个,太强了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-80-Remove-Duplicates-from-Sorted-ArrayII

链接:https://www.javajike.com/article/3216.html

« leetCode-79-Word-Search
leetCode-81-Search-in-Rotated-Sorted-ArrayII»

相关推荐

QR code