LeetCode 26 -删除排序數組中的重複項 --數組-雙指針--簡單

類似題目：

 LeetCode27 移除元素 --數組--雙指針--簡單 （移除指定目标元素）

而本題是數組中相同的元素

解題思路：

需要原地删除，不需要大于O（1）的空間，那麼如何不全部向前移動，而是前後的兩個元素比較并覆寫？

雙指針解法：

一個慢指針和一個快指針，i為慢指針，j為快指針，當nums[i]==nums[j],增加j跳過重複項

當nums[i]！=nums[j]時，需要i向後移動一位并将j位置的元素指派給它，也即是将nums[j]指派給nums[i+1].直到j到達數組末尾

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

//C++
class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
     {
      if (nums.size() == 0) return 0;
       int n = 0;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i]!=nums[n])
            {
                n+=1;
                nums[n]=nums[i];//前一個值更新為後一個值
            }
        }
        return n+1; 
    }
};
           

算法複雜度分析

時間複雜度：O(n)  假設數組的長度是 nn，那麼 ii 和 jj 分别最多周遊 nn 步

空間複雜度：O(1)