7.删除有序数组中的重复项(快慢指针)

文章目录

题目简介
题目解答
- 解法一：暴力解法
- - 复杂度分析：
- 解法二：双指针(快慢指针)
- - 代码：
  - 复杂度分析：
题目链接

大家好，我是晓星航。今天为大家带来的是相关的讲解！😀

题目简介

在这里插入图片描述

题目解答

解法一：暴力解法

在这里插入图片描述
这里我们创建一个新的数组来存放我们遍历完成过后的元素，将未重复的元素添加到我们的新数组，最后返回新数组的长度.length即可，但是我们题目不允许额外创建空间，因此我们还是采取第二种双指针的解法。

复杂度分析：

在这里插入图片描述

解法二：双指针(快慢指针)

在这里插入图片描述
使用双指针来解体，慢指针指向可覆盖位置，快指针用来扫描指向非重复元素，当快指针指向的元素不等于慢指针指向的元素，我们就将快指针的值覆盖到满指针上，慢指针前进一步。(i为慢指针，j为快指针)
要考虑的情况：

数组长度为 0 的情况
数组含有重复元素的情况
数组不含有重复元素的情况
图示解法(来源于力扣官方解法)：

虽然我们数组下标为5的元素不是我们想要的，但是因为我们数组下标是从0开始的，所以我们返回长度直接返回slow的值5即可。

代码：

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n==0) {
            return 0;
        }
        int fast = 1;
        int slow = 1;
        while(fast < n) {
            if (nums[fast] != nums[fast-1]) {
                nums[slow] = nums[fast];
                slow++;
            }
            ++fast;
        }
        return slow;
    }
}

注意这里的数组是递增数组，即代表他是有序的。
在这里插入图片描述
先判断数组是否为空，如果为空直接返回0即可

创建快慢指针，slow慢指针，fast快指针

使用while循环判断，如果快指针的值和他前面一个元素的值不相等，我们就让慢指针的值等于快指针当前的值并加加。如果快指针的值和他前面一个元素的值相等那么快指针直接加加，慢指针不变。直至快指针fast遍历完整个数组之后(fast>=n - 数组长度)，整个while循环结束，此时慢指针得到的新数组就是我们所要的无重复项数组。