字符串的非重複字符

給定一個字符串* Str的ASCII字符，編寫僞代碼以刪除其中存在的重複元素。例如，如果給定的字符串是「土豆」，那麼輸出必須是「Pota」。額外的限制是，該算法必須在原地。字符串的非重複字符

我寫了一個程序，其中包含255個元素的bool數組，並保持它們的值爲false。在遍歷字符串時，我將它們的值更改爲true以將它們標記爲已訪問並以這種方式獲得另一個唯一值字符串。通過這種方式，我使用了恆定的空間。有沒有更好的方法來做到這一點。

來源

2011-07-16 algo-geeks

您所使用的詞語「另一個字符串」，也許，只是也許，你有2個字符串？原地的想法是，你用同一個字符串來做。但是，也許你只是指「另一個字符串內容」，所以是的，那就沒問題。爲了說明：給出了字符串，並在其開始處指定了兩個指針，然後使讀取指針每次讀取一個字符，只有在字符尚未處於寫入中時才寫入（並因此增加寫入指針）你的255表。

來源

2011-07-16 13:36:13

您需要一個布爾值數組您的字母表大小爲（例如，26爲小寫拉丁字母）。然後遍歷字符串，並檢查每個字母是否相應的數組字段爲真。如果不是，請將其設置爲true。然後刪除這封信。要刪除字母，請記下已經刪除了多少字母，然後將每個字母複製到左側。由於這聽起來像是功課，所以我把這些僞代碼的寫法留給你。

來源

2011-07-16 13:34:08

爲了使您的解決方案到位，而不是使用輸出數組，只需將輸入數組中的下一個字符左移到當前位置，無論何時要刪除字符。

僞代碼：

for each position in input_array: 
    c=input_array[position] 
    if we have already seen c 
     shift left all characters position+1 by one character. 
     position=position-1 // so that we process this character in the next iteration 
    else 
     mark c as seen 
    end if

來源

2011-07-16 13:34:24 MAK

該算法在第一次替換後會運行到無限循環。如果您將字符'i + 1'複製到'i'，然後再次查看'i'，您會發現您已經看到了該字符，因此您將'i + 1'複製到'i'並查看在'我'再次等... –

@ Space_C0wB0y：謝謝，更新了我的答案。 – MAK

但現在你已經使它成爲一個n^2的解決方案，如果這是一個家庭作業問題，我不認爲這將足夠:) –

下面是一些僞代碼：

seen is array of 256 boolean, initially all false 
output position is start of string 
for each position in string: 
    c is char at position 
    if seen[c] is false: 
     set seen[c] to true 
     set char at output position to c 
     increment output position

輸出字符串在output position結束。不要忘記設置輸出字符串的長度或者根據不同的編程語言添加它的終止符。

來源

2011-07-16 14:13:52 MRAB

字符串的非重複字符

回答

相關問題