在不使用遞歸的情況下刪除字符串中的重複字符

給您一個字符串。開發一個函數來刪除該字符串中的重複字符。字符串可以是任何長度。你的算法必須在空間中。如果你希望你可以使用恆定大小的額外空間，而不依賴於字符串大小。你的算法必須具有O（n）的複雜性。在不使用遞歸的情況下刪除字符串中的重複字符

我的想法是定義一個大小爲26的整數數組，其中第0個索引對應於字母a的第25個索引，並將所有元素初始化爲0. 因此，我們將整個字符串移動一次並且當我們遇到一封信時，它將在期望的索引處遞增該值。

然後我們將再次移動字符串，如果所需索引值爲1，我們會打印出該字母，否則我們不打印。

以這種方式，時間複雜度是O（n），並且所用的空間是恆定的，而不管字符串的長度如何！

如果有人可以想出更好的效率的想法，這將是非常有益的！

來源

2011-08-05 Poulami

想這是一個家庭作業：P任何編程語言的約束？或僞代碼是好的？例如，如果它是PHP，你可以追加到一個數組，並且大小是可變的，只使用多達你所走過的字符數，並且檢查一個字符是否被檢查是in_array（例如） – Purefan

I不要認爲假定字符串只包含'a'到'z'是公平的。 Unicode中有超過100萬個碼點。 –

@purefan這不是一個家庭作業問題，因爲你已經可以看到我已經將它標記爲採訪qs .. – Poulami

您也可以使用bitset而不是附加數組來跟蹤找到的字符。根據哪些字符（a-z或更多）被允許，您可以相應地調整位集。這需要比整數數組更少的空間。

來源

2011-08-05 06:51:00 murrekatt

您的解決方案絕對符合O（n）時間標準。如果允許的字母表很大（Unicode超過一百萬個字符），則可以使用普通散列，而不是數組。這裏是你的（未優化！）紅寶石算法：

def undup(s) 
    seen = Hash.new(0) 
    s.each_char {|c| seen[c] += 1} 
    result = "" 
    s.each_char {|c| result << c if seen[c] == 1} 
    result 
end 

puts(undup "") 
puts(undup "abc") 
puts(undup "Olé") 
puts(undup "asdasjhdfasjhdfasbfdasdfaghsfdahgsdfahgsdfhgt")

這使得兩次經過串，由於哈希查找不到線性的，你是好。

你可以說Hashtable（就像你的數組）使用恆定的空間，雖然很大，因爲它的大小超出了字母表的大小。即使字母表的大小大於字符串的大小，它仍然算作恆定的空間。

這個問題有很多變化，其中很多都很有趣。要真正到位，可以先排序;這給出了O（n log n）。在合併過程中，您忽略了dups的合併類型有所不同。實際上，這個「無外部哈希表」限制出現在Algorithm: efficient way to remove duplicate integers from an array（也標記爲面試問題）。

另一個常見的面試問題始於一個簡單的字符串，然後他們說，現在好了一百萬字符的字符串，現在好了一個有1000億字符的字符串，等等。當您開始考慮大數據時，事情變得非常有趣。

無論如何，你的想法很不錯。它通常可以如下調整：使用一個集合，而不是一個字典。穿過繩子。對於每個角色，如果它不在該組中，請添加它。如果是，刪除它。集合佔用較少的空間，不需要計數器，並且如果字母表很小，可以實現爲位集，並且該算法不需要兩次通過。

Python實現：http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/

來源

2011-08-05 07:18:44

在不使用遞歸的情況下刪除字符串中的重複字符

回答

相關問題