Benjamin
Benjamin

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

[leetcode]448. Find All Numbers Disappeared in an Array

輸入的數字陣列長度為N,理想上其中應包含1~N各一個,請回傳缺少了哪些數字。
題目原文

題目:448. Find All Numbers Disappeared in an Array


第一版,建表記錄存在的數字

我的方法是使用布林陣列建個表,數字1存在就將表中的索引0標為true,反正數值最大就是N,我只要宣告個長度N的陣列就足夠使用。

不過這方法有些要求,首先建表必須知道表要多大,所以題目提供數字範圍的情況才可以使用;此外範圍太大也可能導致過多的記憶體消耗甚至超過題目限制;如果範圍很大但要記錄的數字不多的話也可能浪費較多空間。

這方法以這題的要求正好合用。輸入陣列的長度N在1~100000之間,其中數值的範圍在1~N之間,只要標示哪些數字有傳入,最後再檢查一次表中哪些數字沒標示過,收集起來就是解答。

執行效率和程式碼

實際上後來也沒想到更好的方法,因此接下來就分享討論區看到的其他做法了。


其他方法,不使用額外空間的方法

這是寫在題目最後的敘述:「你是否寫出不使用額外空間,時間O(n)(線性時間)的做法?」我自己沒想到,所以這是參考自討論區的方法。

它並非在額外的空間標示該數字存在,而是在原本輸入的陣列標示,同時又不影響後續的判斷。

以輸入陣列為[4,3,1,1]為例:

第一個數字確認到4的存在,將第四個數字標為負數,以此代表4已記錄,陣列變為[4,3,1,-1];
第二個數字讓陣列變為[4,3,-1,-1];
第三個數字轉為正整數(畢竟沒有第'負一'個數字)再記錄,陣列變為[-4,3,-1,-1];
第四個數字轉為正整數仍標在第一個數字,陣列仍是[-4,3,-1,-1]。

最後依序確認一次整個陣列,發現其中第二個數字是正的,也就代表前面的檢查中沒有發現過數字2,這就是解答。

將正負數判斷用絕對值函式精簡之後的程式和效率如下:

精簡後的程式

我的方法較快的可能原因有幾個,關於第一個迴圈將有傳入標記為true的部分,不只布林比整數的位元來的少,另外因為我的寫法是不加判斷直接寫true,少了一些判斷和計算的功夫;第二個迴圈檢查數字1~N是否在先前記錄過,純粹的true/false判斷也會比數字比大小的過程來得快。

至於明明不使用額外空間,執行結果使用的空間卻比我的方法略多的原因,我認為是在過程中計算使用的空間也被計算所造成的。

參考的討論區解答:https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/solutions/1583741/time-o-n-space-o-1/

CC BY-NC-ND 4.0

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

Loading...

Comment