這道題要我們從有序數組中去除重複項，題目難度雖然被歸為 easy 等級，但在條件限制上的討論，蠻多東西可以釐清討論的。 英文方面寫得蠻長，記得要看到最後因為有寫一些限制如 :

• O(1) extra memory
• The relative order of the elements should be kept the same.

所以不能用 Set 或另開 array 去寫。另外也花了些篇幅去說明，只要原 array 前面長度部分內，有把所有不重複數字列出來就好，不需要在意後面 array 的元素和 array 的長度。

兩個重點條件限制 :

• O(1) extra memory

• The relative order of the elements should be kept the same.

以下使用各種方式來解題，當作練習

思路

使用快慢指針來遍歷 array :

• lower 和 faster 都從 index 0 開始
• lower之前的 index 都是處理好的數字

接下來開始循環邏輯 :

• 若 faster == 0 ，則為初始狀態，快慢指針都前進。

• 因為定義 lower 之前的 index 均為處理好的資料，故若條件 nums[lower - 1 ] != nums[faster] ，則 快慢指針都前進，並把 nums[lower] 換成 nums[faster]

解答

class Solution {
	public int removeDuplicates( int[] nums ) {
		int faster = 0;
		int lower = 0;
		while (faster < nums.length) {
			if ( faster == 0 || nums[lower - 1] != nums[faster] ) {
				nums[lower++] = nums[faster++];
			} else {
				faster++;
			}
		}
		return lower;
	}
}

其它思路

一樣是使用快慢指針來遍歷 array ，最開始時兩個指針都指向第一個數字，但

• 兩個指針指的數字相同，則快指針向前走一步
• 如果不同，則慢指針先向前一步，把慢指針對應 index 數字換成快指針對應 index 數字，再來快指針前進

可以發現這樣的邏輯下，慢指針的位置，就代表目前置換過的 index 。當快指針走完整個數組時，慢指針當前位置，就代表最後更新的位置，故 lower + 1 就是數組中不同數字的個數。

解答

class Solution {
	public int removeDuplicates( int[] nums ) {
		int faster = 0;
		int lower = 0;
		while (faster < nums.length) {
			if ( nums[lower] == nums[faster] ) {
				++faster;
			} else {
				nums[++lower] = nums[faster++];
			}
		}
		return lower + 1;
	}
}

上面邏輯也可以換成 for loop 也可以解 !

class Solution {
	public int removeDuplicates( int[] nums ) {
		int lower = 0;
		for ( int faster = 0; faster < nums.length; faster++ ) {
			if ( nums[faster] != nums[lower] ) {
				nums[++lower] = nums[faster];
			}
		}

		return lower + 1;
	}
}

時間空間複雜度

時間複雜度: O(N)

遍歷 nums 需 O(N)

空間複雜度：O(1)

因為禁止開額外空間，此題強制 O(1)

Vocabulary

參考資料

• Grandyang