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

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

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

兩個重點條件限制 :

  • In-place，這個片語意思，代表直接對輸入的 data-structure 進行操作，不另開額外空間。in-place algorithm 會應用在一些不希望大量增加記憶體使用量，是拿時間換取空間的概念。

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

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

解答

使用快慢指針來遍歷 array :

  • lower 和 faster 都從 index 0 開始
  • lower之前的 index 都是處理好的數字
  • faster 代表是現在掃描到的 index

接下來開始循環邏輯 :

  • 若 faster == 0 ，則為初始狀態，兩個指針都先前進。

  • 因為定義 lower 之前的 index 均為處理好的資料，代表不重複值。若條件 nums[lower - 1 ] != nums[faster] 成立，代表 lower 當下位置可以替換，把 nums[lower] 換成 nums[faster]之後，兩個指針都前進 ; 若條件不成立，則就只有 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;
	}
}

faster == 0 || nums[lower - 1] != nums[faster] 中的 faster == 0 很重要，避免 lower - 超出 array range

nums[lower++] = nums[faster++]; 是個蠻簡潔不錯的寫法，可以在賦值完之後，才再讓指針前進。想提醒自己這個部分，才特別註記筆記這題的。

再來刷一次題時，發現第 0 個元素一定會保留，故第二個元素開始就可以了

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        faster = 1
        lower = 1
        while faster < len(nums):
            if nums[lower - 1] != nums[faster]:
                nums[lower] = nums[faster]
                lower += 1
                
            faster +=1
        
        return lower

思考了一下，這題的條件 : The relative order of the elements should be kept the same. 並沒有什麼用，上面的寫法完全不會改變相對排序。

其它思路

一樣是使用快慢指針來遍歷 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;
	}
}

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        index = 0
    
        for i in range(1, n):
            if nums[i] != nums[index]:
                index +=1
                nums[index] = nums[i]
        
        return index + 1

時間空間複雜度

時間複雜度: O(N)

遍歷 nums 需 O(N)

空間複雜度：O(1)

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

參考資料