數組優先於set還是map？

Question

我最近接受了海灣地區一家公司的採訪（CA，USA）。其中一個問題是簡單地找出一個字符串是否有重複的字符（我簡化了一個冗長的問題）。

eg: 
input : "qwerrty" 
output : True 

我用python的實現代碼。

我給出了一個解決方案，它使用一個集合來跟蹤迭代過程中遇到的元素。

但是面試官要我使用數組[255]跟蹤中遇到的字符。

雖然我使用其中一方還是挺舒服的，我的意見是使用一套簡單，因爲我們是在浪費255個字符的空間時，我們使用數組。這是因爲（正如我們都知道的），最初我們創建一個arr [255] = 0所有元素爲零，然後將ASCII等效索引值增加1.

另一方面，集合只會花費內存元素訪問。

因爲他（種）認爲使用了一組數組我很想知道，如果他是技術上是正確的。在這種情況下數組是首選的嗎？如果是這樣，爲什麼？

Answer 1

有一點要注意這個問題是，如果有是僅含有C可能不同的字符可以是字符串，那麼對於任意字符串所得到的長度C + 1或更高就可以自動返回存在重複無甚至看着絃樂，因爲它們的字符太多，都是唯一的（這是工作中的鴿子原理）。這對於思考這個特定問題的結構很重要。

接下來，請注意，您甚至不需要一堆計數器。每個角色只需要一位就可以脫身，因爲您只需要知道您是否從未看過某個角色（0），或者在您遍歷該數組時是否曾經看過該角色（1）。這意味着你需要每個角色一位。如果您的字大小爲W，這意味着基於陣列的解決方案需要大約C/W的存儲空間總計機器字。

讓我們想象一下，你用C = 256的工作（比如，例如，每個字符是一個字節的值）的機器上有32位字長（W = 32）。這意味着你需要八個機器字來存儲位數組，這是一個可以忽略不計的存儲空間，並且可以很容易地初始化爲0.現在，考慮一下你的設置實現。如果使用散列表，將會有某種內部數組用於存儲所有內容。您還需要空間來存儲有關散列函數的信息，通常您會在某處緩存集合的大小。這將會像三個機器字一樣消耗大小和散列函數信息，這會留下五個空間單詞。如果散列表通常實現並且每個條目佔用一個機器字，那麼如果有四個條目或更少的散列表，則這種方法只會節省空間，這不太可能發生。如果你的散列表經過優化並直接存儲char值，那麼你可以存儲多達5個單詞的字符（20個字符），而不會發生任何衝突，但是如果你試圖保持低的載入率，你可能會調整表格的大小你看到了10個左右的字符。因此，在短期，除非你有一個非常短字符串，哈希表的做法可能會使用更多的內存和散列的開銷會很高。陣列方法可能會更快。

另一方面，假設您要在字符串中存儲任意的Unicode字符。現在，C = 1,114,112（感謝，維基百科），即使是64位字大小，你也需要一組17,408個機器字來存儲每個可能字符一位。這是一個很多的存儲空間，它需要一段時間來初始化它。現在，如果輸入的字符串是「合理的」而不是病態的，那麼很可能你會在字符串的早期找到一個重複的元素（如果字符串是完全隨機的，那麼在生日之前悖論，你只需要√（2C）字符，然後平均得到重複），所以構建哈希表可能需要更少的空間。但是，如果字符串是病態構建的，以便每個字符都是唯一的，但計算散列函數的常數因子開銷，哈希表大小調整等可能意味着您的方法將比基於陣列的方法慢，但這是一個不尋常的用例。

總結：

• 如果可能的字符數小（認爲ASCII），基於陣列的方法很可能將是一個很大更快，存取效率。

• 如果可能的字符數很大（認爲是Unicode），那麼基於數組的方法在合理的輸入上可能會更慢，記憶效率更低，但對於病態選擇的輸入可能會比基於散列的方法。

現在，說，除非代碼在一個緊湊的循環運行，你可能會說，不是「只使用了一組」以外的任何使代碼很難最小造福於整個程序的效率閱讀。出於這個原因，一個合理的答案將是「使用該組，除非有一個原因，然後切換到基於數組的數據支持它。」

Answer 2

我相信時間複雜性與空間複雜度分析是您面試官尋找的實際答案。 空間明智，兩種情況都是O（N）。 明智的做法是，將字符添加到集合中不是O（1），但是將1添加到數組中的值爲O（1）。 所以一般來說，使用數組將消耗相同數量的內存，但時間更少。