leetcode （Remove Duplicates from Sorted Array）

Title： Remove Duplicates from Sorted Array    26

Difficulty：Easy

原題leetcode位址：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

1. 采用雙引用（指針），時間&空間複雜度如下：

時間複雜度：O(n)，一層while循環，周遊的是數組的長度。

空間複雜度：O(n)，沒有申請額外的空間。

/**
     * 采用雙指針（快慢指針）來記錄周遊的坐标，開始是兩個指針都是指向第一個數字，
     *      如果兩個指針指向的數字相同，快指針向前一步，慢指針不動
     *      如果兩個指針指向的數字不同，兩個指針都向前一步，同時需要把快指針的值指派給慢指針的值
     *      最後，快指針周遊完，慢指針的位置就是傳回的值（坐标+1）
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        if (nums.length <= 0) {
            return 0;
        }

        int slow = 0;
        int qick = 0;

        while (qick < nums.length) {
            if (nums[slow] == nums[qick]) {
                ++qick;
            } else {
                nums[++slow] = nums[qick++];
            }
        }
        return slow + 1;
    }
           

2.  采用雙引用（指針），上述時while循環，這裡的是for循環。時間&空間複雜度如下：

時間複雜度：O(n)，一層for循環，周遊的是數組的長度。

空間複雜度：O(n)，沒有申請額外的空間。

/**
     * for循環，i相當于上述的qick，機相當于上述的slow
     * @param nums
     * @return
     */
    public static int removeDuplicates1(int[] nums) {
        if (nums.length <= 0) {
            return 0;
        }

        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != nums[j]) {
                nums[++j] = nums[i];
            }
        }

        return j + 1;
    }