Benjamin
Benjamin

新人工程師,偶爾分享工作心得(預計?

[leetcode]217. Contains Duplicate

判斷輸入的數字陣列是否包含重複的數字。
題目原文

題目:217. Contains Duplicate
關鍵字:集合(set)

集合(set):只能用來判斷「有沒有」而不能判斷「有幾個」,也不能判斷加入先後的資料結構,可以很快速的加入資料以及判斷資料是否存在。


第一版,直覺的想法

「直接把允許內容重複的陣列轉成集合,如果集合的長度比陣列短就表示有重複的值」,聽起來蠻合理的對吧?

陣列轉集合

雖然通過了但資源使用的效率落在後頭,這點完全符合預期,畢竟我們只要確認是否有重複,全部去重複是不必要的工作。


第二版,符合實務想法的集合使用

依序確認陣列的所有數字,如果集合內發現已經存在就表示重複,集合裡沒有就加入集合,直到全數確認完畢都沒發現重複就表示不重複。

符合實務想法的集合使用

從執行時間的落點可以發現,這應該算是本題的主流解法,或者與主流解法效率相同,只要對集合有點了解就能想到,並不困難。


第三版,先加入再確認結果

記錄原本集合的長度,不做判斷地加入新的數字後再確認集合是否確實加入新元素(長度變長),以此判斷這個數字是否重複。

先加入再確認集合元素數量

由於原本使用的contains實際上也是在集合內比對是否有相同的元素,隨著集合元素數量增加比對花費的時間也會變長,省去這段搜索的功夫直接確認長度的變化會更快,效率的表現上也超越原本大多數解答的執行時間。


第四版,發掘函式沒想到的特性

set.add(num) 除了原本不存在就加入,存在就跳過之外,它的回傳值還可以用來分辨集合原本是否存在耶!

說實話,以前的我大概做到上一步就結案了,這次是想著「加入新元素時其實也會判斷原本有沒有吧?」心血來潮研究之後,注意到原始碼的說明。

Set的原始碼註解

在了解這個事實之前,第二版程式使用contains和add在檢查每個數字的時候都多做一次集合內的搜尋,也就不意外改進之後效率能再次提升了。

使用add的回傳值判斷是否重複

這是我能想到最精簡,也是最有效率的寫法了。


番外第一版,先排序再比較

呼叫排序功能排序後,再依序檢查所有數字是否與相鄰的元素相等。

先排序再比較

速度比第一版的直接轉為集合略快,但記憶體用的更多,畢竟排序的過程多少也需要額外空間,最核心的還是這方法也多費了額外不必要的功夫。


有些時候解題不一定需要多特別的想法,只是多知道了一點知識就能讓結果出現差異。這次研究的成果雖然不大,不過以後只要是使用集合的場合都能精進,或許也算是一天進步1%的表現?

CC BY-NC-ND 2.0

Like my work?
Don't forget to support or like, so I know you are with me..

Loading...

Comment