如何高效對有序數組/鏈表去重？

作者 | labuladong

來源 | labuladong

我們知道對於數組來說，在尾部插入、刪除元素是比較高效的，時間複雜度是 O(1)，但是如果在中間或者開頭插入、刪除元素，就會涉及數據的搬移，時間複雜度為 O(N)，效率較低。

所以對於一般處理數組的演算法問題，我們要儘可能只對數組尾部的元素進行操作，以避免額外的時間複雜度。

這篇文章講講如何對一個有序數組去重，先看下題目：

顯然，由於數組已經排序，所以重複的元素一定連在一起，找出它們並不難，但如果毎找到一個重複元素就立即刪除它，就是在數組中間進行刪除操作，整個時間複雜度是會達到 O(N^2)。而且題目要求我們原地修改，也就是說不能用輔助數組，空間複雜度得是 O(1)。

其實，對於數組相關的演算法問題，有一個通用的技巧：要盡量避免在中間刪除元素，那我就先想辦法把這個元素換到最後去。

這樣的話，最終待刪除的元素都拖在數組尾部，一個一個 pop 掉就行了，每次操作的時間複雜度也就降低到 O(1) 了。

按照這個思路呢，又可以衍生出解決類似需求的通用方式：雙指針技巧。具體一點說，應該是快慢指針。

我們讓慢指針slow走左後面，快指針fast走在前面探路，找到一個不重複的元素就告訴slow並讓slow前進一步。

這樣當fast指針遍歷完整個數組nums後，nums[0..slow]就是不重複元素，之後的所有元素都是重複元素。

看下演算法執行的過程：

再簡單擴展一下，如果給你一個有序鏈表，如何去重呢？其實和數組是一模一樣的，唯一的區別是把數組賦值操作變成操作指針而已：

對於鏈表去重，演算法執行的過程是這樣的：

最後，近期準備寫寫一些簡單實用的數組/鏈表技巧。那些稍困難的技巧（比如動態規劃）雖然秀，但畢竟在現實生活中不容易遇到。恰恰是一些簡單常用的技巧，能夠在不經意間，讓人發現你是個高手 ^_^。