預(yù)計閱讀時間:5 分鐘我們知道對于數(shù)組來說,在尾部插入、刪除元素是比較高效的,時間復(fù)雜度是 O(1),但是如果在中間或者開頭插入、刪除元素,就會涉及數(shù)據(jù)的搬移,時間復(fù)雜度為 O(N),效率較低。 所以對于一般處理數(shù)組的算法問題,我們要盡可能只對數(shù)組尾部的元素進(jìn)行操作,以避免額外的時間復(fù)雜度。 這篇文章講講如何對一個有序數(shù)組去重,先看下題目: 顯然,由于數(shù)組已經(jīng)排序,所以重復(fù)的元素一定連在一起,找出它們并不難,但如果毎找到一個重復(fù)元素就立即刪除它,就是在數(shù)組中間進(jìn)行刪除操作,整個時間復(fù)雜度是會達(dá)到 O(N^2)。而且題目要求我們原地修改,也就是說不能用輔助數(shù)組,空間復(fù)雜度得是 O(1)。 其實,對于數(shù)組相關(guān)的算法問題,有一個通用的技巧:要盡量避免在中間刪除元素,那我就先想辦法把這個元素?fù)Q到最后去。 這樣的話,最終待刪除的元素都拖在數(shù)組尾部,一個一個 pop 掉就行了,每次操作的時間復(fù)雜度也就降低到 O(1) 了。 按照這個思路呢,又可以衍生出解決類似需求的通用方式:雙指針技巧。具體一點說,應(yīng)該是快慢指針。 我們讓慢指針 這樣當(dāng) 看下算法執(zhí)行的過程: 再簡單擴(kuò)展一下,如果給你一個有序鏈表,如何去重呢?其實和數(shù)組是一模一樣的,唯一的區(qū)別是把數(shù)組賦值操作變成操作指針而已: 對于鏈表去重,算法執(zhí)行的過程是這樣的: 最后,近期準(zhǔn)備寫寫一些簡單實用的數(shù)組/鏈表技巧。那些稍困難的技巧(比如動態(tài)規(guī)劃)雖然秀,但畢竟在現(xiàn)實生活中不容易遇到。恰恰是一些簡單常用的技巧,能夠在不經(jīng)意間,讓人發(fā)現(xiàn)你是個高手 ^_^。 |
|