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

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

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

说明:

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

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

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

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

示例 1：

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

示例 2：

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

提示：

• 0 ≤ nums.length ≤ 3 × 10；
• -100 ≤ nums[i] ≤ 100；
• nums已按升序排列

思路

使用双指针法。其中i是慢指针，j是快指针。遍历数组，做出如下判断：

• 当nums[i] == nums[j]时，递增j以跳过重复项；
• 当nums[i] != nums[j]时，把nums[j]的值复制到nums[i+1]，再递增i；
• 重复上述过程，直到j到达数组末尾位置。

考虑一种特殊场景，数组nums中没有重复元素。按照上面的方法，每次比较nums[i]都不等于nums[j]，则将j指向的元素原地复制一遍，这个操作其实是不必要的，因此应该添加一个判断：当重复元素的个数大于1时才进行复制。

代码

Rust：

// 0ms, 2.2MB
impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        if nums.len() == 0 {
            return 0;
        }
        let mut slow_index = 0;
        for fast_index in 1 .. nums.len() {
            if nums[slow_index] != nums[fast_index] {
                if fast_index - slow_index > 1 {
                    nums[slow_index+1] = nums[fast_index];
                }
                slow_index += 1;
            }
        }
        (slow_index + 1) as i32
    }
}