這一題在原文網址上列為簡易型的題目，看了題目之後，只要你熟悉一些基本的資料結構，應該可以很快想出不錯的解法．題目輸入是兩個 integer array，然後輸出一個 array，這個 array 包含的元素要出現在兩個輸入的 array 裡．
若用最直覺的想法，你可以做一個 for loop 在第一個輸入 array 上，把每一個元素和第二個輸入 array 的元素相比較．以這樣的做法來看，時間複雜度將會是 O(n2)．以這個題目來說，這樣的時間複雜度並不理想．所以得再想想一個比較好的處理方式．
我在寫這題時一開始就想到利用 hash table 來運作，因為 hash table 有極佳的 O(1) 的動作速度．所以一開始把第一個輸入 array 所有的元素透過一個 for loop 加入到 hash table．然後再將第二個輸入 array 利用另一個 for loop 來查看是否有同樣的數字已經存在於 hash table 之中．如果有的話，它就是我們要尋找的對象，但把它加入到輸出的結果裡，這裡是用一個 List 來代表．最後再將整個 List 轉換成 array 輸出，這樣的轉換只需要 O(n). 因此，整個時間複雜度將是 O(n+n+n)．有二個 for loop 和最後的轉換，所以一共是三個 n.程式碼如下:
最後我還發現了 LeetCode 提供了與其他同樣語言解法的比較．上述的解法打敗使用同樣語言 75% 的解法．我想這是以他們電腦執行速度來計算的．由此可見，上述的程式碼在最佳化上還有很大的空間可以改進．
0 意見:
張貼留言