leecode刷題（1）-- 刪除排序數(shù)組中的重復(fù)項(xiàng)

刪除排序數(shù)組中的重復(fù)項(xiàng)

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

注意：題目中的數(shù)組已經(jīng)排序！

示例：

給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素。

代碼如下：

public class RemoveDuplicates {

   public static 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;
   }

    public static void main(String[] args) {
        int[] nums = {1,1,2};
        int len = removeDuplicates(nums);
        for (int i = 0; i < len; i++) {
            System.out.println(nums[i]);           
        }
    }
}

算法：雙指針法

數(shù)組完成排序后，我們可以放置兩個指針 i 和 j ，其中 i 是慢指針，而 j 是快指針。只要 nums[i] = nums[j]，我們就增加 j 以跳過重復(fù)項(xiàng)。

當(dāng)我們遇到 nums[j] != nums[i] 時，跳過重復(fù)項(xiàng)的運(yùn)行已經(jīng)結(jié)束，因此我們必須把它（nums[j]）的值復(fù)制到 nums[i + 1]。然后遞增 i，接著我們將再次重復(fù)相同的過程，直到 j 到達(dá)數(shù)組的末尾為止。

復(fù)雜度

• 時間復(fù)雜度：O(n)， 假設(shè)數(shù)組的長度是 n，那么 i 和 j 分別最多遍歷 n 步。
• 空間復(fù)雜度：O(1)。