【LeetCode - Java】26. 删除有序数组中的重复项 （简单）

【LeetCode - Java】26. 删除有序数组中的重复项 （简单）

目录

• • 1. 题目描述
  • 2. 解题思路
  • 3. 代码实现
  • • 3.1 双指针
    • 3.2 优化双指针
    • 3.3 对比

1. 题目描述

2. 解题思路

这个解题思路用语言描述似乎不太方便，于是乎我又画了一个图来展现算法运行的某一部分过程，其中i是代表对数组进行遍历的索引（快指针），而pre则是代表待修改元素的索引（慢指针），那么图中还有一个index是什么来的呢？其实这个index索引的初衷是为了记住已经修改好的最后一个元素值是多少，在算法当中通过修改后把i的值赋给index来实现。后来画完这个图之后一看，咦？index下的值不就是跟pre-1的值是一样的吗？那就不用浪费多一个变量的空间进行储存了。

3. 代码实现 3.1 双指针

public int removeDuplicates(int[] nums) {
        int index = 0;
        int pre = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[index]) {
                nums[pre] = nums[i];
                index = i;
                pre++;
            }
        }
        return pre;
    }

尽管在时间上表现很好，但在空间上似乎很糟糕，但其实只创建了两个变量而已。

3.2 优化双指针

public int removeDuplicates(int[] nums) {
        int pre = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[pre - 1]) {
                nums[pre] = nums[i];
                pre++;
            }
        }
        return pre;
    }

经过优化以后内存消耗终于稍微能看一下了，这里只申请了一个变量，但还是只排在中等位置。

3.3 对比

emmm… 这题好像没什么好对比的，时间复杂度都为O(n)，n为数组的长度，空间复杂度为O(1)