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

题目:删除有序数组中的重复项

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

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

• 示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

• 示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

• 提示：

0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列

思路1

可以顺序遍历数组,遇到重复的元素跳过去,出现新元素就为新数组赋值,将新数组长度加一

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int removeDuplicates(int[] nums) { // 总时间复杂度O(n)
    if (nums.length == 0) {
        return 0;
    }
    int newLength = 0;
    // 顺序遍历数组
    for (int i = 0; i < nums.length; i++) { // 时间复杂度O(n)
        // 遇到重复的元素跳过去
        while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
            i++;
        }
        // 为新数组赋值,且新数组长度加一
        nums[newLength++] = nums[i];
    }
    return newLength;
}

思路2

可以放置两个指针i和j，其中i是慢指针，而j是快指针。只要nums[i] = nums[j]，我们就增加j以跳过重复项。

当我们遇到nums[j] ≠ nums[i]时，跳过重复项的运行已经结束，因此我们必须把nums[j]的值赋值到nums[i + 1]。然后递增i，接着我们将再次重复相同的过程，直到j到达数组的末尾为止。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int removeDuplicates(int[] nums) { // 总时间复杂度O(n)
    if (nums.length == 0) {
        return 0;
    }
    // 慢指针
    int i = 0;
    // 快指针
    for (int j = 1; j < nums.length; j++) { // 时间复杂度O(n)
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}