26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 0;
        for(int i = 1; i<nums.length; i++){
            if(nums[j]!=nums[i]){
                j++;
                nums[j] = nums[i];
            }
                
           
        }
        return j+1;
    }
}

方法：双指针法

算法 数组完成排序后，我们可以放置两个指针 $i$ 和 $j$，其中 $i$ 是慢指针，而 $j$ 是快指针。只要 $nums[i]=nums[j]$，我们就增加 $j$ 以跳过重复项。 当我们遇到 $nums[j]\ne nums[i]$ 时，跳过重复项的运行已经结束，因此我们必须把它（$nums[j]$）的值复制到 $nums[i+1]$。然后递增 $i$，接着我们将再次重复相同的过程，直到 $j$ 到达数组的末尾为止。 复杂度分析

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