26 删除排序数组中的重复项——Easy

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

方法：双指针

• 思路
  • 对于排序数组，设置两个指针 \(fast\) 和 \(slow\)，其中 \(slow\) 是慢指针，\(fast\) 是快指针
  • 当 \(nums[slow] = nums[fast]\)，就增加 \(fast\) 以跳过重复项
  • 当 \(nums[slow]\neq nums[fast]\) ，跳过重复项的动作结束，交换 \(nums[slow+1]\) 和 \(nums[fast]\) ，然后递增 \(fast\) 和 \(slow\)
  • 再次重复相同的过程，直到 \(fast\) 到达数组的末尾为止
• code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2) {
            return nums.size();
        }
        int slow = 0;
        for (int fast = 1; fast < nums.size(); ++fast) {
            if (nums[slow] != nums[fast]) {
                swap(nums[++slow], nums[fast]);
            }
        }
        return slow + 1;
    }
};

• 复杂度分析
  • 时间复杂度：\(O(n)\)，假设数组的长度是 \(n\)，那么 \(fast\) 和 \(slow\) 分别最多遍历 \(n\) 步。
  • 空间复杂度：\(O(1)\)