2020/2/15

题目描述

• 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

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

示例

示例 1:

  给定数组 nums = [1,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。

  你不需要考虑数组中超出新长度后面的元素。

相关标签

数组
双指针

解题思路

• 本题可以分别使用两个快慢指针来完成重复元素的删除。
• 快指针用于寻找数组中出现的下一个不同的元素
• 慢指针指向的元素用于与快指针找的的元素进行比较，从而判断快指针指向的元素是否为新的不同元素；
• 新找的数存储在慢指针的后一位置，并且慢指针右移一位

源代码

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let len = nums.len();
        if len <= 1 {
            return len as i32;
        }
        let (mut left, mut right) = (0, 0);
        while right < len {
            // println!("left: {}, right: {}, len: {}", left, right, len);
            if nums[left] == nums[right] {
                right += 1;
            } else {
                left += 1;
                nums[left] = nums[right];
                right += 1;
            }
        }        
        (left+1) as i32
    }
}

• 执行用时 : 0 ms, 在所有 Rust 提交中击败了100.00%的用户
• 内存消耗 : 2.2 MB, 在所有 Rust 提交中击败了87.50%的用户

总结

本题较为简单，总结略过。