0080. Remove Duplicates from Sorted Array II (Medium)

Question

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array ** in-place** with O(1) extra memory.

Example 1

1

Given nums = [1,1,1,2,2,3],

1

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

1

It doesn't matter what you leave beyond the returned length.

Example 2

1

Given nums = [0,0,1,1,1,1,2,3,3],

1

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

1

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference , which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

1
2
3
4
5

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

分析/解題

給定一個已排序的陣列nums，將其重復超過2次的部分捨棄掉，
且使用in-place的方式來操作(在原陣列操作)，回傳最終結果的長度。

這題算是之前的0083. Remove Duplicates from Sorted List (Easy)的延伸，說真的我認為這題不該當作Medium難度XD

再次提醒，當題目要求使用in-place的時候，
對一些語言的確是可以真的用刪掉單點 的方式來處理(例如Python)，
但刪除這件事情也是較耗時的操作，所以沒特別要求的話，
請依照題目希望你的方向來撰寫(面試則依照面試官的限制條件 )。

我們先來講筆者直觀想到的解法，再來提leetcode上另一位高手的解。

直觀而言，要怎麼能夠知道有沒有碰到3個 以上的重復呢？
最直接的方式就是使用一個cnt變數來記錄。
同時，為了要確認是否是重複的數，
我們需要記錄上一次開始重復的數last。

那麼步驟就會像這樣：

1. 如果nums長度 ≤ 2 的話，表示完全不用更動，
   直接回傳nums的長度 即可。
2. 將last設為nums[0], cnt設為1, 預計要覆蓋的** index j設為1。**
3. 令i從1開始一個迴圈來遍歷整個nums:
   3-a. 如果nums[i]不等於last 的話，表示數字不同 ，
   必須將其覆蓋到j的位置 。
   同時，我們必須更新last為nums[i]，j要遞增，
   cnt要重設為1 (用來做下一次比較)。
   3-b. 否則，如果兩者相等且cnt小於2 ，
   代表重複未超過2次，同樣要進行複寫和遞增j，但cnt要遞增 。
4. 當整個迴圈完畢以後，j 應該是位在處理過後的陣列的尾端+1 的位置。
   所以回傳j即可代表新的陣列的總長 。

聽起來有點多，但其實寫起來並不困難，
但還有更厲害的解法XD

這邊提供了LeetCode上StefanPochmann 的解，
簡單來說呢，我們可以換個思路：
由於整個陣列是排序過的 ，當我們遍歷陣列時，
某個數字應不應該要覆蓋到index上 ，
(筆者之前的解法將這個index叫做j，相當於這個解裡的i)
取決於前面兩個數字是否跟它一樣 ；
都一樣的話，就產生了三個相同的數 的狀況，
自然不需要再被取用，且由於排序的關係，
我們只需要比較前面兩個數字中較前面的那個 即可。

當i小於2時，直接無條件覆蓋( 因為不可能重複超過2次)；
當遍歷到的値n大於num[i-2] 時，代表數字不一樣 或重複未超過2次 ，
則應將其值覆蓋過去並遞增i 。

各自寫成程式碼如下：

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，我們需要遍歷整個陣列，且儲存用的輔助變數只有常數個)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~